传送门：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.****.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=;i*i<=x;i++)
{
if(x%i==)
{
res=res-res/i;
while(x%i==)
x/=i;
}
}
if(x>)res=res-res/x;
return res;
} //求某个值的欧拉函数值
ll q(ll x,ll y,ll MOD)
{
ll res=;
while(y){
if(y&)res=res*x%MOD;
x=(x*x)%MOD;
y>>=;
}
return res;
}//快速幂
char * change(ll a){
char s[];
int ans = ;
while(a){
s[ans++]=(a%)+'';
a/=;
}
s[ans]='\0';
strrev(s);
return s;
}//数字转字符串
char *solve(ll a,char s[],ll c){
ll i,ans,tmp,b;
ans=;b=;tmp=ol(c);
ll len=strlen(s);
for(i=;i<len;i++)b=(b*+s[i]-'')%tmp;
b += tmp;
ans=q(a,b,c);
return change(ans);
}//欧拉降幂
int main()
{
ll a,c = ,b,d;
char s[];
int t;
for(scanf("%d",&t);t--;){
scanf("%I64d %I64d %s",&a,&b,s);
printf("%s\n",solve(a,solve(b,s,ol(c)),c));//注意第一次降幂用的是 ol(c)
}
return ;
}