MMOD29 - CALCULATE POW(2004,X) MOD 29
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#include <math.h>
long f(long a,long n)
{
if(n==1)
return a;
else if(n%2!=0)
return a*f(a,n-1)%29;
else
{
double y=pow(f(a,n/2),2);
long x=long(y);
if(y-x>0.1)
return (x+1)%29;
else return x%29;
}
}
main()
{
long x[30],n,a,b,c,KQ;
for(long i=0;i<=28;i++)
x[i]=(21*i)%29;
while(scanf("%ld",&n)&&n>0)
{
a=f(2,2*n+1)-1;
for(long i=0;i<=28;i++)
if(f(22,n+1)-1==x[i])
b=i;
if(f(3,n+1)%2!=0)
c=(f(3,n+1)-1)/2;
else c=(f(3,n+1)+28)/2;
//printf("%ld %ld %ld %ld ",a,b,c,f(22,n+1));
KQ=a*b*c%29;
printf("%ld\n",KQ);
}
//getch();
}