Cod sursa(job #3342845)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 25 februarie 2026 21:31:23
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ll;
const int NMAX = 1e6;

bool sieve[NMAX + 10];
vector<ll> primes;
void compute_primes(){
    sieve[0] = sieve[1] = true;
    for(int i = 2; i * i <= NMAX; i++){
        if(sieve[i]) continue;
        for(int j = i * i; j <= NMAX; j += i)
            sieve[j] = true;
    }
    for(int i = 2; i <= NMAX; i++){
        if(!sieve[i]) primes.push_back(i);
    }
}
ll power(ll baza, ll exp){
    ll rez = 1;
    while(exp){
        if(exp & 1) rez *= baza;
        baza *= baza;
        exp >>= 1;
    }
    return rez;
}

pair<ll, ll> divisors(ll x){
    ll number_of_divisors = 1;
    ll sum_of_divisors = 1;

    for(int i = 0; i < primes.size() && primes[i] * primes[i] <= x; i++){
        ll factor = primes[i];
        ll exponent = 0;
        while(x % factor == 0){
            exponent++;
            x /= factor;
        }
        if(exponent == 0) continue;
        number_of_divisors = number_of_divisors * (exponent + 1);
        sum_of_divisors = sum_of_divisors * ((power(factor, exponent + 1) - 1) / (factor - 1));
    }
    if(x > 1){
        number_of_divisors *= 2;
        sum_of_divisors *= (x + 1);
    }

    return {number_of_divisors, sum_of_divisors};
}
int main()
{
    freopen("ssnd.in", "r", stdin);
    freopen("ssnd.out", "w", stdout);
    compute_primes();

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        ll x;
        scanf("%llu", &x);
        pair<ll, ll> result = divisors(x);
        printf("%llu %llu\n", result.first, result.second);
    }
    return 0;
}