快速冪

要算 ,最暴力的方法就是乘 次,不過這樣的時間複雜度是 ,太慢了。

利用 的性質,我們可以把指數拆開,例如:

乘上自己會得到 、再乘自己會得到 ,每次指數都會變兩倍,只要做 次就可以拿到 了。因此,可以用這樣的方式在 的時間算出答案:

1
2
3
4
5
6
7
8
9
10
const ll MOD = 1000000007;
ll fp(ll a, ll b){
int ans = 1;
while(b > 0){
if(b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}