[FOJ1759 Super A^B mod C]某数论公式的应用

【题目】
求A^B % C
A,C<=1e9。
B<=10^1000000
【算法分析】
师傅说有一个公式
A^x=A^(x % phi(c) + phi(c) )    (mod c)
然后直接套。
【其它】1A
【CODE】
#include #include #include #include using namespace std;
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;
}

加入对话

7条评论

留下评论

您的电子邮箱地址不会被公开。