【题目】
求A^B % C
A,C<=1e9。
B<=10^1000000
【算法分析】
师傅说有一个公式
A^x=A^(x % phi(c) + phi(c) ) (mod c)
然后直接套。
【其它】1A
【CODE】
#include
typedef long long lld;
const lld N=1005555;
lld A,B,C,phi;
char str[N];
void makephi(){
lld x=C,i;
phi=C;
for (i=2;i*i<=x;i++)
if (x%i==0){
phi=phi/i*(i-1);
while (x%i==0) x/=i;
}
if (x!=1) phi=phi/x*(x-1);
}
void String_to_Number(){
bool flag=false;
lld i,j,Len=strlen(str+1);
B=0;
for (i=1;i<=Len;i++){
B=B*10+str[i]-‘0’;
if (B>=phi){
flag=true;
B%=phi;
}
}
if (flag) B+=phi;
}
lld Pow_mod(lld x,lld cf){
if (!cf) return 1;
lld res=Pow_mod(x,cf/2);
res*=res; res%=C;
if (cf%2) res*=x;
res%=C;
return res;
}
int main(){
while (scanf("%I64d %s %I64d",&A,str+1,&C)!=EOF){
makephi();
String_to_Number();
printf("%I64dn",Pow_mod(A,B));
}
return 0;
}
这题是我出的本意是考察baby-step + 枚举的思想找指数循环节后来发现有这个简单的公式……
回复ad饕饕不绝:Orz。我又不会baby step= =。
回复edward_mj:所以比赛的时候没人过……
bsgs没什么。。。C是质数吧..
回复jsn1993:显然不是。
x%phi(c)+phi(c)能直接变成x%phi(c)么?
哦 不可以 ac不一定互素