class="markdown_views prism-dracula"> Description Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000). Input There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space. Output For each testcase, output an integer, denotes the result of A^B mod C. Sample Input 3 2 4
2 10 1000
Sample Output 1
24 写出来代码之后在FZU疯狂提交，疯狂TLE。后来换个编译器就A了。
交了一晚上真郁闷。。。 因为b太大，用普通快速幂求余肯定不行了。
所以就要对n进行降幂。
然后就用到了一个数论的知识：指数循环节：
#include #include #include using namespace std; typedef long long int LL; const int MAXL=1e7; char s[MAXL+50]; LL euler(LL n)//找b的欧拉函数值 { LL ans=n,a=n; for(LL i=2; i*i<=a; i++) { if(a%i==0) { ans=ans/i*(i-1); while(a%i==0) a/=i; } } if(a>1) ans=ans/a*(a-1); return ans; } LL fast_pow(LL a,LL b, LL c) { LL ans=1; a%=c; while(b) { if(b&1) ans=ans*a%c; a=a*a%c; b>>=1; } return ans%c; } int main() { LL a,c; while(~scanf("%lld%s%lld",&a,s,&c)) { int len=strlen(s); int flag=0; LL sum=0; LL x=euler(c); for(int i=0; i10+(s[i]-'0'); if(sum>x) flag=1; if(flag==1) sum%=x; } LL ans; if(flag==0) ans=fast_pow(a,sum,c); else ans=fast_pow(a,sum+x,c); printf("%lld ",ans); } return 0; }