Cod sursa(job #2969434)

Utilizator matthriscuMatt . matthriscu Data 23 ianuarie 2023 00:37:28
Problema Fractii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 1000005

int main() {
    ifstream fin("fractii.in");
    ofstream fout("fractii.out");

    int n;
    fin >> n;

    vector<int> lp(n + 1, 0);
    vector<int> primes;
    long long ans = 1;

    for (int i = 2; i <= n; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            primes.push_back(i);
        }

        for (size_t j = 0; i * primes[j] <= n && primes[j] <= lp[i]; ++j)
            if (i * primes[j] <= n)
                lp[i * primes[j]] = primes[j];

        int c = i, prod = i;

        while (c != 1) {
            int fact = lp[c];
            prod = prod / fact * (fact - 1);
            while (c % fact == 0)
                c /= fact;
        }

        ans += prod * 2;
    }

    fout << ans << '\n';
}