Cod sursa(job #1496282)

Utilizator cojocarugabiReality cojocarugabi Data 4 octombrie 2015 18:03:20
Problema Suma si numarul divizorilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
# include <bits/stdc++.h>
# define x first
# define y second
using namespace std;
ifstream fi("ssnd.in");
ofstream fo("ssnd.out");
vector < int > primes;
bitset < 1000005 > p;
pair < int , long long > ans(long long n)
{
    pair < int , long long > d = {1,1};
    for (auto it : primes)
    {
        if (1ll * it * it > n) break;
        int cnt = 1;
        long long c = 1;
        while (!(n%it)) n /= it,++cnt,c *= it;
        d.x *= cnt;
        d.y *= (c * it - 1) / (it - 1);
    }
    if (n != 1) d.x *= 2,d.y *= (n*n - 1) / (n - 1);
    return d;
}
int main(void)
{
    int t;
    for (int i = 2;i <= 1e6;++i) p[i] = 1;
    for (int i = 4;i <= 1e6;i += 2) p[i] = 0;
    for (int i = 3;i*i <= 1e6;++i)
        if (p[i])
            for (int j = i*i;j <= 1e6;j += i + i)
                p[j] = 0;
    for (int i = 2;i <= 1e6;++i)
        if (p[i]) primes.push_back(i);
    ios_base :: sync_with_stdio(0);
    fi>>t;
    long long n;
    while (t --)
    {
        fi>>n;
        pair < int , long long > d = ans(n);
        fo << d.x << ' ' << d.y << '\n';
    }
    return 0;
}