Cod sursa(job #2135558)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 18 februarie 2018 22:26:20
Problema Suma si numarul divizorilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <cstdio>

using namespace std;

bool ciur[50002];
long long prime[50002];

int len;

void init(){
    for(int i = 4; i <= 50000; i += 2)
        ciur[i] = 1;
    for(int i = 3; i * i <= 50000; i += 2){
        if(!ciur[i]){
            for(int j = i * i; j <= 50000; j += i * 2)
                ciur[j] = 1;
        }
    }
    prime[++len] = 2;
    for(int i = 3; i <= 50002; i += 2){
        if(!ciur[i])
            prime[++len] = (long long)i;
    }
}


int main()
{
    freopen("ssnd.in", "r", stdin);
    freopen("ssnd.out", "w", stdout);
    int t;
    scanf("%d", &t);
    init();
    for(int numar = 1; numar <= t; ++numar){
        long long n;
        scanf("%lld", &n);
        int nrdiv = 1, sumdiv = 1, div = 1, exp;
        while(prime[div] <= n && div <= len){
            long long put = 1LL; exp = 0;
            while(n % prime[div] == 0){
                n /= prime[div];
                put *= prime[div];
                exp++;
            }
            put *= prime[div];
            nrdiv *= (exp + 1);
            sumdiv *= (put - 1) / (prime[div] - 1);
            div++;
        }
        if(n > 1)
            nrdiv *= 2;
        printf("%d %d\n", nrdiv, sumdiv);
    }
    return 0;
}