Cod sursa(job #2338584)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 7 februarie 2019 17:06:46
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#include <vector>
#define lld long long
#define nmax 1000005
using namespace std;
FILE *fin=fopen("ssnd.in","r");
FILE *fout=fopen("ssnd.out","w");

vector<int>primes;
bool erat[nmax+2];
int t;
lld n;
lld ans1, ans2;

lld expPow(lld x, int p)
{
    lld ans = 1;
    while (p)
    {
        if (p&1)
        {
            ans = ans*x;
            p|=1;
        }
        x*=x;
        p>>=1;
    }
    return ans;
}
void ciur()
{
    for (int i=2;i<=nmax;++i)
    {
        if (!erat[i])
        {
            primes.push_back(i);
            for (int j=i;j<=nmax;j+=i)
            {
                erat[j] = true;
            }
        }
    }
}
int main()
{
    fscanf(fin,"%d",&t);
    ciur();
    for (int i=1;i<=t;++i)
    {
        fscanf(fin,"%lld",&n);
        lld cn = n;
        ans1 = ans2 = 1;
        for (int i=0;i<primes.size()&&primes[i]*primes[i]<=cn && n>1;++i)
        {
            if (n%primes[i])
            {
                continue;
            }
            int d = 0;
            while (n%primes[i] == 0)
            {
                ++d;
                n/=primes[i];
            }
            ans1 *= (d+1);
            ans2 *= ((expPow(primes[i], d+1)-1)/(primes[i] -1));
        }
        if (n!=1)
        {
            ans1 *= 2;
            ans2 *= ((expPow(n,2)-1)/(n-1));
        }
        fprintf(fout,"%lld %lld\n",ans1,ans2);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}