題意#
這題要求你計算 \(a^b \pmod{10^9+7}\) 的結果，並且會給你多筆測資。
思路#
如果直接用迴圈把 \(a\) 乘上 \(b\) 次，遇到 \(b\) 很大的時候一定會超時（TLE）。
這時候，就需要用到「快速冪」演算法。
快速冪的核心概念，是把指數 \(b\) 拆解成二進位。
舉例來說，想算 \(a^{13}\)，\(13\) 的二進位是 \(1101_2\)，也就是 \(8 + 4 + 1\)。
所以 \(a^{13} = a^8 \times a^4 \times a^1\)。
我們只要在迴圈裡不斷把底數平方（\(a \to a^2 \to a^4 \to a^8\)）。
同時看當前指數 \(b\) 的最低位是不是 1。
如果是 1，就把當前的底數乘進答案裡。
這樣原本要算 \(b\) 次的乘法，瞬間降到只需要做 \(\log_2(b)\) 次，非常快。
記得每次乘法後都要對 \(10^9+7\) 取模，以免產生溢位。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
int p = 1e9+7; // 題目要求的模數
// 快速冪函式，計算 n 的 x 次方並對 p 取模
int f(int n, int x) {
int ret = 1; // 儲存最終結果
// 迴圈每次將 x 右移一位 (相當於除以 2)，底數 n 則自乘平方
for (; x; x>>=1, n = n*n%p) {
// 如果當前 x 的最低位是 1 (代表有對應的二進位位元)
if (x&1) ret = ret*n%p;
}
return ret;
}
signed main() { WA();
int t;
// t 筆測資
for (cin >> t; t--;) {
int a, b; cin >> a >> b;
cout << f(a, b) << '\n'; // 直接呼叫快速冪函式並輸出
}
}
