Cod sursa(job #1111821)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 19 februarie 2014 10:00:02
Problema Suma si numarul divizorilor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#define mod 9973
using namespace std;
ifstream f("ssnd.in");
ofstream g("ssnd.out");

int t, prim[80000], nr, lim, prod, k;
long long sum, X;
bitset < 1000005 > viz;

void ciur()
{
    prim[++nr]=2;
    for (int i=3; i<=1000000; i+=2)
        if (!viz[i])
        {
            prim[++nr]=i;
            if (i<=1000)
                for (int j=i*i; j<=1000000; j+=i)
                    viz[j]=1;
        }
}

int log_pow(int baza, int exp)
{
    int res=1;
    while (exp)
    {
        if (exp%2) res*=baza, res%=mod;
        baza*=baza; baza%=mod; exp/=2;
    }
    return res;
}

int main()
{
    f>>t; ciur();
    while (t--)
    {
        f>>X; lim=sqrt(X); prod=sum=1;
        for (int i=1; prim[i]<=lim && X>1 && i<=nr; ++i)
            if (X%prim[i]==0)
            {
                k=0;
                while (X%prim[i]==0) ++k, X/=prim[i];
                prod*=(k+1);
                int x1=log_pow(prim[i], k+1)-1, x2=log_pow(prim[i]-1, mod-2);
                sum*=x1*x2;
                if (sum>mod) sum%=mod;
            }
        if (X>1) prod*=2, sum*=(X+1);
        g<<prod<<' '<<sum%mod<<'\n';
    }
    return 0;
}