传送门：http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3151
时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte
描述
H1N1 like to solve acm problems.But they are very busy, one day they meet a problem. Given three intergers a,b,c, the task is to compute a^(b^c))%317000011. 1412, ziyuan and qu317058542 don't have time to solve it, so the turn to you for help.
输入
The first line contains an integer T which stands for the number of test cases. Each case consists of three integer a, b, c seperated by a space in a single line. 1 <= a,b,c <= 100000
输出
For each case, print a^(b^c)%317000011 in a single line.
样例输入
2
1 1 1
2 2 2
样例输出
1
16
思路：
直接暴力用欧拉降幂2次来做的
欧拉降幂公式：
A^B%C=A^( B%Phi[C] + Phi[C] )%C (B>=Phi[C])
数学方面的证明可以去：http://blog.csdn.net/Pedro_Lee/article/details/51458773 学习
注意第一次降幂的时候Mod值取的是317000011的欧拉函数值
恩，这样用时是600MS，耗时还是很高的。
其实因为317000011是质数，它的欧拉函数值是本身减1.于是就可以转换到下式
a^(b^c) % p = a^( (b^c)%(p-1) )%p
直接搞个快速幂就好了
给出欧拉降幂的代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #define ll long long using namespace std; ll ol(ll x) { ll i,res=x; for(i=2;i*i<=x;i++) { if(x%i==0) { res=res-res/i; while(x%i==0) x/=i; } } if(x>1)res=res-res/x; return res; } //求某个值的欧拉函数值 ll q(ll x,ll y,ll MOD) { ll res=1; while(y){ if(y&1)res=res*x%MOD; x=(x*x)%MOD; y>>=1; } return res; }//快速幂 char * change(ll a){ char s[10000]; int ans = 0; while(a){ s[ans++]=(a%10)+'0'; a/=10; } s[ans]=' '; strrev(s); return s; }//数字转字符串 char *solve(ll a,char s[],ll c){ ll i,ans,tmp,b; ans=0;b=0;tmp=ol(c); ll len=strlen(s); for(i=0;i<len;i++)b=(b*10+s[i]-'0')%tmp; b += tmp; ans=q(a,b,c); return change(ans); }//欧拉降幂 int main() { ll a,c = 317000011,b,d; char s[100000]; int t; for(scanf("%d",&t);t--;){ scanf("%I64d %I64d %s",&a,&b,s); printf("%s ",solve(a,solve(b,s,ol(c)),c));//注意第一次降幂用的是 ol(c) } return 0; }