10.快速幂

快速幂时间复杂度O(log k)，k是指数
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll qmi(ll a, ll k, ll p) {
 5     ll res = 1;
 6     while (k) {
 7         if (k & 1) { //如果k的个位是1的话
 8             res = res * a % p;
 9         }
10         k >>= 1;
11         a = a * a % p;
12     }
13     return res;
14 }
15 int main() {
16     ios::sync_with_stdio(false);
17     cin.tie(0);
18     cout.tie(0);
19     int n;
20     cin >> n;
21     while (n--) {
22         ll a, k, p;
23         cin >> a >> k >> p;
24         cout << qmi(a, k, p) << endl;
25     }
26     return 0;
27 }