Cod sursa(job #1612806)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 25 februarie 2016 01:15:56
Problema Suma si numarul divizorilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>

const long long NMAX = 1000010;

int T;
long long N;
long long NRD, SUMD;

char ciur[NMAX];

void functieCiur () {
    ciur[0] = ciur[1] = 1;
    long long p = 2;
    while (p * p <= NMAX) {
        for (long long i = p * p; i <= N; i += p) {
            ciur[i] = 1;
        }

        while (ciur[++p] == 1);
    }
}

int main () {
    freopen ("ssnd.in", "r", stdin);
    freopen ("ssnd.out", "w", stdout);

    functieCiur ();

    scanf ("%d", &T);
    while (T--) {
        scanf ("%lld", &N);

        NRD = SUMD = 1;

        for (long long f = 2; f * f <= N;) {
            long long flap = 1;
            long long p = 0;
            while (N % f == 0) {
                N /= f;
                flap *= f;
                p++;
            }

            NRD *= (p + 1);
            SUMD *= ((flap * f) - 1) / (f - 1);

            while (ciur[++f] == 1);
        }

        if (N != 1) {
            NRD *= 2;
            SUMD *= ((N * N) - 1) / (N - 1);
        }

        printf ("%lld %lld\n", NRD, SUMD);
    }

    return 0;
}