# Cod sursa(job #31490)

Utilizator Data 16 martie 2007 09:22:38 Suma divizorilor 100 cpp done Arhiva de probleme 1.12 kb
``````#include<math.h>
#include<stdio.h>
long long a,b,sir[100000],j,fi,bb[1000],aa[1000],x,y,fact,m,aux,aux2,k;
long long functie(long long a , long long b)
{
long long c=0,d=1,n=9901,i;
for(i=1;b;sir[i]=b%2,b/=2,i++);
sir[0]=i-1;
for(i=sir[0];i>0;i--)
{
c*=2;
d=(d*d)%n;
if (sir[i]==1)
{
c++;
d=(d*a)%n;
}
}
return d;
}
int main()
{
freopen("sumdiv.in","r",stdin);
freopen("sumdiv.out","w",stdout);
scanf("%lld %lld",&x,&y);
fact=1;
while(x!=1)
{
fact++;
m=0;
while (x%fact==0) {x/=fact;m++;}
if (m)
{
aa[++aa[0]]=fact;
bb[++bb[0]]=m;
}
if (fact>sqrt(x)) break;
}
if (x!=1)
{
aa[++aa[0]]=x;
bb[++bb[0]]=1;
}
for(j=1;j<=bb[0];j++)
bb[j]*=y;
k=1;
for(j=1;j<=aa[0];j++)
{
if (aa[j]%9901!=1)
{
aux=functie(aa[j],bb[j]+1);
if (aux) aux--;
if (aux==0) aux=9900;
aux2=functie(aa[j]-1,9899);
k=(k*aux*aux2)%9901;
}
else
{
aux=(bb[j]+1)%9901;
k=(k*aux)%9901;
}
}
printf("%lld\n",k);
printf("\n");
return 0;
}
``````