Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).
思路一：
十進(jìn)制做法，把B分解，一步一步求A^B mod C,這樣最多是1000W。TLE。測(cè)試數(shù)據(jù)組肯定很多》=10
思路二：
求A^x=1 mod C，直接求x=phi(C)就行。然后求A^B=A^(B mod C) mod (C)。
尼瑪，我是傻逼啊，居然用x=C-1(C是質(zhì)數(shù))x=C(C是合數(shù))?。。。。。。。?！簡單的數(shù)論啊，這個(gè)就給跪了??！
詭異的地方了我一直TLE啊，后的都優(yōu)化了嘛，100W啊，怎么還是TLE?。縒A我都能接受，然后就去x=phi(C)啊。我擦擦擦?。。。?br />
取x=phi(C);啊啊啊 啊
#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxn 1000000
char B[maxn+5];
long long phi(long long n)
{
long long ans=1,i;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
{
n/=i;
ans*=i-1;
while(n%i==0)
{
n/=i;
ans*=i;
}
}
}
if(n>1)
ans*=n-1;
return ans;
}
long long strmod(long long t)
{
int i,len;
long long r=0;
len=strlen(B);
for (i=0;i<len;i++)
{
r=(r*10+B[i]-'0') % t;
}
return r;
}
long long power(long long a,long long b,long long c)
{
long long r;
r=1;a=a%c;
while (b)
{
if (b&1)
r=(r*a) % c;
a=(a*a)%c;
b>>=1;
}
return r % c;
}
int main()
{
long long A,b,C;
while (scanf("%I64d%s%I64d",&A,&B,&C)==3)
{
long long t;
A=A%C;
t=phi(C);
b=strmod(t);
printf("%I64d\n",power(A,b,C));
}
return 0;
}
尼瑪，我真心是傻逼啊?。?！