知道降幂公式这题就很好办了 B>=Phi(c)的时候可以降幂然后快速幂计算,否则就直接快速幂计算。
这里的大数对小数取模直接利用取模性质按位取就行了。
//A^B %C=A^( B%phi(C)+phi(C) ) %C #include <cstdlib> #include <cstring> #include <cstdio> #include <iostream> #include<string> #include<cmath> using namespace std; typedef __int64 ll; int phi(int x) { int i,j; int num = x; for(i = 2; i*i <= x; i++) { if(x % i == 0) { num = (num/i)*(i-1); while(x % i == 0) { x = x / i; } } } if(x != 1) num = (num/x)*(x-1); return num; } ll quickpow(ll m,ll n,ll k) { ll ans=1; while(n) { if(n&1) ans=(ans*m)%k; n=(n>>1); m=(m*m)%k; } return ans; } char tb[1000015]; int main() { ll a,nb; int c; while(scanf("%I64d%s%d",&a,tb,&c)!=EOF) { int PHI=phi(c); ll res=0; for(int i=0;tb[i];i++) { res=(res*10+tb[i]-'0'); if(res>c)break; } if(res<=PHI) { printf("%I64d\n",quickpow(a,res,c)); } else { res=0; for(int i=0;tb[i];i++) { res=(res*10+tb[i]-'0')%PHI; } printf("%I64d\n",quickpow(a,res+PHI,c)); } } return 0; }
FZU - 1759 Super A^B mod C 降幂公式,布布扣,bubuko.com
FZU - 1759 Super A^B mod C 降幂公式
原文:http://blog.csdn.net/t1019256391/article/details/37595993