FZU 1759-Super A^B mod C(指数循环节)

题目地址：FZOJ 1759
题意：求 A^B mod C的值(1<=A,C<=1000000000,1<=B<=10^1000000).
思路：此题的B值特别的大，我们要实行降幂处理，其实有这么一个公式可以解决：

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#pragma comment(linker, "/STACK:102400000,102400000")
typedef __int64 LL;
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
const double esp=1e-6;
using namespace std;
const int Maxn=1e6+10;
//直接法求欧拉函数
int Euler(int n)
{int m=floor(sqrt(n+0.5));int ans=n;for(int i=2;i<=m;i++){if(n%i==0){ans=ans/i*(i-1);while(n%i==0)n/=i;}}if(n>1)ans=ans/n*(n-1);return ans;
}
//快速乘法
LL Mul(LL a,LL b,LL mod)
{LL res=0;while(b>0){if(b&1) res=(res+a)%mod;b>>=1;a=(a+a)%mod;}return res;
}
//快速幂
LL modxp(LL a,LL b,LL mod)
{LL res=1;while(b>0){if(b&1) res=Mul(res,a,mod);b>>=1;a=Mul(a,a,mod);}return res;
}LL Solve(LL a,char str[],LL mod)
{LL len=strlen(str);LL res=0;LL t=Euler(mod);if(len<=15){for(int i=0;i<len;i++){res=res*10+str[i]-'0';}}else{for(int i=0;i<len;i++){res=res*10+str[i]-'0';res%=t;}if(res<0) res+=mod;}return res;
}int main()
{LL a,c,res;char b[Maxn];while(~scanf("%I64d %s %I64d",&a,b,&c)){res=Solve(a,b,c);printf("%I64d\n",modxp(a,res,c));}return 0;
}