题目:
给定a,b
求出:a^a^a....^a(b个a)
输入:
a ,b
输出
运算结果
样例:
2 3
输出:16
范围:a,b<=10^9
我们首先可以得到答案的式子:ans=a^(a^(b-1))
然而(a^(b-1))作为指数太大了,必须取模
令y=(a^(b-1)),p=1e9+7
y=k*φ(p)+(y%φ(p))
因为x^φ(p)Ξ1(mod p)
所以a^φ(p)%p=1
所以a^y=a^(y%φ(p))
因为p是素数,所以φ(p)=p-1
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 using namespace std;
6 int Mod=1000000007;
7 long long a,b,ans,s;
8 long long qpow(long long x,int y,int mo)
9 {
10 long long res=1;
11 while (y)
12 {
13 if (y&1) res=(res*x)%mo;
14 x=(x*x)%mo;
15 y>>=1;
16 }
17 return res;
18 }
19 int main()
20 {
21 cin>>a>>b;
22 s=qpow(a,b-1,Mod-1);
23 ans=qpow(a,s,Mod);
24 cout<<ans;
25 }