Cod sursa(job #476687)

Utilizator proxenetuNea Caisa proxenetu Data 12 august 2010 01:17:50
Problema Fractii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <bitset>

using namespace std;

#define maxN    1000100

bitset <maxN> Prim;
vector < pair <int, int> > V[maxN];
int N;

int pow (int number, int exp) {
    if (exp == 0)
        return 1;
    if (exp == 1)
        return number;

    int x = pow(number, exp / 2);
    x *= x;

    return exp %  2 == 1 ? x * number : x;
}
int main () {
    int i, x, j, k, product;
    long long sum = 0;

    freopen("fractii.in", "r", stdin);
    freopen("fractii.out", "w", stdout);

    scanf("%d", &N);
    Prim.set();

    for (i = 2; i <= N; i += 2) {
        Prim[i] = false;
        for (x = i, j = 0; x %  2 == 0; x /= 2, j ++);
        V[i].push_back(make_pair(2, j));
    }

    for (i = 3; i <= N; i += 2)
        if (Prim[i]) {
            for (j = i; j <= N; j += i) {
                Prim[j] = false;
                for (x = j, k = 0; x % i == 0; x /= i, k ++ );
                V[j].push_back(make_pair(i, k));
            }
        }

    for (i = 2; i <= N; ++ i) {
        product = 1;
        for (j = 0; j < (int) V[i].size(); ++ j)
            product *= (V[i][j].first - 1) * pow(V[i][j].first, V[i][j].second - 1);
        sum += product;
    }

    printf("%lld\n", 2LL * sum + 1);
}