Cod sursa(job #2264254)

Utilizator preda.andreiPreda Andrei preda.andrei Data 19 octombrie 2018 22:21:37
Problema Fractii Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>

#define NMAX 1000000

long long int tot[NMAX + 1];
char is_not_prime[NMAX + 1];

int main()
{
    FILE *fin = fopen("fractii.in", "r");
    FILE *fout = fopen("fractii.out", "w");

    int n;
    fscanf(fin, "%d", &n);

    for (int i = 2; i <= n; i += 1) {
        tot[i] = 1;
    }

    for (int i = 2; i <= n; i += 1) {
        if (is_not_prime[i]) {
            continue;
        }

        tot[i] = i - 1;

        long long int power = 1LL * i * i;
        while (power <= n) {
            for (long long int j = power; j <= n; j += power) {
                tot[j] *= power / i * (i - 1);
            }
            power *= i;
        }

        for (long long int j = 1LL * i * i; j <= n; j += i) {
            is_not_prime[j] = 1;
        }
    }

    long long int res = 1;
    for (int i = 2; i <= n; i += 1) {
        res += tot[i] * 2;
    }

    fprintf(fout, "%lld\n", res);
    return 0;
}