Cod sursa(job #3284902)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 12 martie 2025 12:26:44
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
#define int long long
const int DIM = 1e6;
bitset <DIM + 3>ciur;
vector<int> prime;

inline void prelucru() {
    ciur[0] = ciur[1] = 1;
    for(int i=2; i*i<=DIM; i++)
        if(!ciur[i])
            for(int j=i*i; j<=DIM; j+=i) ciur[j] = 1;
    for(int i=2; i<=DIM; i++)
        if(!ciur[i]) prime.push_back(i);
}

inline int expRapida(int A, int n) {
    ///returneaza A^n
    int p = 1;
    while(n) {
        if(n % 2 == 1) p *= A;
        A *= A, n /= 2;
    }
    return p;
}

inline void solve(int n) {
    int d = 0, sumDiv = 1, nrDiv = 1;
    while(n > 1) {
        int e = 0;
        while(n % prime[d] == 0) e++, n /= prime[d];
        if(e) {
            nrDiv = 1LL * nrDiv * (e + 1);
            sumDiv = 1LL * sumDiv * ((expRapida(prime[d], e + 1) - 1) / (prime[d] - 1));
        }
        d++;
        if(prime[d] * prime[d] > n && n > 1) {
            nrDiv = 1LL * nrDiv * 2;
            sumDiv = 1LL * sumDiv * (n + 1);
            break;
        }
    }
    fout << nrDiv << " " << sumDiv << '\n';
}

signed main()
{
    prelucru();
    int tt; fin >> tt;
    while(tt--) {
        int x; fin >> x;
        solve(x);
    }

    return 0;
}