指數取模算法

題目：

給定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 }