Cod sursa(job #2145651)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 27 februarie 2018 15:16:07
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <vector>
#include <fstream>

#define DMAX 1000010

std::ifstream fin("fractii.in");
std::ofstream fout("fractii.out");

int n, sol;
std::vector<int> primes;
std::vector<bool> sieve(DMAX);

int pow(int a, int b) {
    if (!b)
        return 1;

    if (b & 1)
        return a * pow(a * a, b >> 1);
    return pow(a * a, b >> 1);
}

int euler(int n) {
    int ind = 1;
    for (int i = 0; n > 1; i++)
        if (n % primes[i] == 0) {
            int exp = -1;
            while (n % primes[i] == 0) {
                exp++;
                n /= primes[i];
            }
            ind *= (primes[i] - 1) * pow(primes[i], exp);
        }
    return ind;
}

void genPrimes() {
    for (int i = 2; i * i <= n; i++)
        if (!sieve[i])
            for (int j = i * i; j <= n; j += i)
                sieve[j] = true;

    primes.push_back(2);
    for (int i = 3; i <= n; i += 2)
        primes.push_back(i);
}

int main() {
    fin >> n;
    genPrimes();

    sol = 1;
    for (int i = 2; i <= n; i++)
        sol += euler(i) << 1;

    fout << sol << '\n';
    fout.close();
    return 0;
}