Cod sursa(job #547875)
Utilizator | Z.Z.Daniel blastoise | Data | 6 martie 2011 19:32:50 |
---|---|---|---|
Problema | Suma si numarul divizorilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.01 kb |
#include <stdio.h>
#include <string.h>
#define MOD 9973
#define size 70000
#define max 1000000
#define len 500000
int i,j,T,d,e,w;
char p[size+5];
int v[len];
long long n,sd,s,nd,pow;
int main()
{
freopen("ssnd.in","r",stdin);
freopen("ssnd.out","w",stdout);
memset(p,0,sizeof(p));
memset(v,0,sizeof(v));
for(i=1;(((i*i)<<1)+(i<<1))<=max;i++)
if((p[i>>3]&(1<<(i&7)))==0)
for(j=(((i*i)<<1)+(i<<1));((j<<1)+1)<=max;j+=((i<<1)+1))
p[j>>3]|=(1<<(j&7));
w=0;
for(i=1;((i<<1)+1)<=max;i++)
if((p[i>>3]&(1<<(i&7)))==0)
v[++w]=((i<<1)+1);
scanf("%d",&T);
for(i=1;i<=T;i++)
{
scanf("%lld",&n);
nd=1;
sd=1;
if(n%2==0)
{
e=0;
s=0;
while(n%2==0)
{
n/=2;
e++;
}
nd*=(e+1);
nd%=MOD;
pow=1;
for(j=0;j<=e;j++)
{
s+=pow;
s%=MOD;
pow*=2;
pow%=MOD;
}
sd*=s;
sd%=MOD;
}
d=1;
do
{
if(n%v[d]==0)
{
e=0;
s=0;
while(n%v[d]==0)
{
n/=v[d];
e++;
}
nd*=(e+1);
nd%=MOD;
pow=1;
for(j=0;j<=e;j++)
{
s+=pow;
s%=MOD;
pow*=v[d];
pow%=MOD;
}
sd*=s;
sd%=MOD;
}
d++;
}
while(n>=v[d]*v[d]);
if(n!=1)
{
s=0;
nd*=2;
nd%=MOD;
s++;
s+=n;
s%=MOD;
sd*=s;
sd%=MOD;
}
printf("%lld %lld\n",nd,sd);
}
return 0;
}