Cod sursa(job #2061192)

Utilizator amaliarebAmalia Rebegea amaliareb Data 8 noiembrie 2017 23:12:08
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
int div[1000005], n, i, j;
long long tot[1000005], sol;

void makeciur(int n)
{
    for(int i = 2; i * i <= n; i++) if(!div[i])
        for(int j = i * i; j <= n; j += i) div[j] = i;
}

void maketot(int n)
{
    tot[1] = 1;
    sol = 1;
    for(i = 2; i <= n; i++)
    {
        if(!div[i]) tot[i] = i - 1;
        else
        {
            int nr = i;
            int pow = 0;
            while(nr % div[i] == 0) nr /= div[i], pow++;
            tot[i] = i / (nr * div[i]) * tot[nr] * (div[i] - 1);
        }
        sol += 2 * tot[i];
    }
}

int main()
{
    f >> n;
    makeciur(n);
    maketot(n);
    g << sol << '\n';
    return 0;
}