Cod sursa(job #3199692)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 2 februarie 2024 15:45:33
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
const int Max = 1000000;
long long pr[Max + 2], k;
bool fr[Max + 2];
long long t, n;

static inline void Ciur() {
    pr[++k] = 2;
    for(long long j = 4; j <= Max; j += 2) fr[j] = true;
    long long i;
    for(i = 3; i * i <= Max; i += 2) {
        if(!fr[i]) {
            pr[++k] = i;
            for(long long  j = i * i; j <= Max; j += i) fr[j] = true;
        }
    }
    while(i <= Max) {
        if(!fr[i]) pr[++k] = i;
        i++;
    }
}

static inline void Calc() {
    long long  nrd = 1, sum = 1;
    fin >> n;
    long long d = 1;
    while(pr[d] * pr[d] <= n) {
        long long e = 0;
        long long p = pr[d];
        while(n % pr[d] == 0) {
            e++;
            p *= pr[d];
            n /= pr[d];
        }

        if(e) {
            sum *= (p - 1) / (pr[d] - 1);
            nrd *= e + 1;
        }

        d++;
    }
    if(n > 1) {
        sum *= (n * n - 1) / (n - 1);
        nrd *= 1 + 1;
    }

    fout << nrd << " " << sum << "\n";
}

int main() {
    Ciur();
    fin >> t;
    while(t--) Calc();

    return 0;
}