快速冪
要算 ，最暴力的方法就是乘 次，不過這樣的時間複雜度是 ，太慢了。
利用 的性質，我們可以把指數拆開，例如：
乘上自己會得到 、再乘自己會得到 ，每次指數都會變兩倍，只要做 次就可以拿到 了。因此，可以用這樣的方式在 的時間算出答案：
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;
}
|
