Cod sursa(job #2440990)

Utilizator AlexNeaguAlexandru AlexNeagu Data 19 iulie 2019 18:08:30
Problema Suma si numarul divizorilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
ifstream cin("ssnd.in");
ofstream cout("ssnd.out");
const int nmax = 1e6 + 5;
vector < int > primes;
vector < bool > sieve(2000005, false);
void eratostene() {
    sieve[1] = true;
    sieve[0] = true;
    for (int i = 2 * 2; i <= nmax; i += 2) sieve[i] = true;
    for (int i = 3; i <= nmax; i += 2)
    if (!sieve[i]) {
        for (int j = i + i; j <= nmax; j += i)
            sieve[j] = true;
    }
    for (int i = 1; i <= nmax; i++) if (!sieve[i]) primes.push_back(i);
}
void solve (ll number) {
    ll cnt = 1, sum = 1;
    ll x = number;
    for (int i = 0; i < primes.size() && primes[i] < (int) sqrt (number) + 1 && x > 1; i++) if (x % primes[i] == 0) {
        ll p = primes[i], cn = 1;
        while (x % primes[i] == 0 && x > 1) {
            x /= primes[i];
            p *= primes[i];
            cn++;
        }
        p--;
        p /= (primes[i] - 1);
        cnt *= cn;
        sum *= p;
    }
    if (x > 1) {
    cnt *= 2;
    sum *= ( (x * x - 1) / (x - 1) );
    }
    cout << cnt << " " << sum << "\n";
}
int main() {
    int n;
    eratostene();
    cin >> n;
    while (n--) {
        ll x;
        cin >> x;
        solve(x);
    }
    return 0;
}