Cod sursa(job #1064379)

Utilizator margikiMargeloiu Andrei margiki Data 21 decembrie 2013 19:25:59
Problema Suma si numarul divizorilor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
# include <fstream>
# include <algorithm>
# include <bitset>
# include <cmath>
# define N_Max 1000000
using namespace std;
ifstream f("ssnd.in");
ofstream g("ssnd.out");
bitset <1000005> p;
long long a[200000];
long long i,j,k,n,VV,d,ndiv,suma,nr,ap,v1,v2;
long long x,X;
long long putere (long long w, long long q)
{
    long long QQ=1;
    w=w%9973;
    while (q>0)
    {
        if (q%2==1)
        {
            QQ=QQ*w%9973;
            --q;
        }
        else
        {
            w=w*w%9973;
            q=q/2;
        }
    }
    return QQ;
}
int main ()
{
    a[1]=2;
    k=1;
    for (i=3; i<=N_Max; i=i+2)
    {
        if (p[i]==0)
        {
            a[++k]=i;
            for (j=3; i*j<=N_Max; j=j+2)
                p[i*j]=1;
        }
    }
    f>>n;
    for (i=1; i<=n; ++i)
    {
        f>>x; X=x;
        ndiv=1; suma=1;
        for (j=1; j<=k && a[j]*a[j]<=X && x!=0; ++j)
        {
            if (x%a[j]==0)
            {
                ap=0;
                while (x%a[j]==0)
                {
                    ++ap;
                    x=x/a[j];
                }
                ndiv=ndiv*(ap+1);
                v1=(putere(a[j],ap+1)-1)%9973;
                v2=putere(a[j]-1,9971)%9973;
                suma=(suma*(v1%9973)*v2)%9973;
            }
        }
        if (x>1)
        {
            ndiv*=2;
            suma=suma*(x+1)%9973;
        }
        g<<ndiv<<" "<<suma<<"\n";
    }


    return 0;
}