Exponentiation
Exponentiation
Compute \(n\) values \(a^b \bmod (10^9 + 7)\). In this problem, \(0^0 = 1\).
Constraints:
- \(1 \le n \le 2 \cdot 10^5\)
- \(0 \le a, b \le 10^9\)
Input:
- First line: integer \(n\) — the number of calculations.
- Next \(n\) lines: two integers \(a\) and \(b\).
Output:
- For each calculation, one line with \(a^b \bmod (10^9 + 7)\).
Example:
Input:
3
3 4
2 8
123 123
Output:
81
256
921450052
Solution
Multiplying \(a\) by itself \(b\) times needs up to \(10^9\) multiplications for one calculation, and there are up to \(2 \cdot 10^5\) calculations. This is too slow.
We use fast exponentiation from the lesson on modular arithmetic. It halves the exponent at each step, so one calculation needs only \(O(\log b)\) multiplications.
All values stay below \(10^9 + 7\), so a product of two values is below about \(10^{18}\) and fits in long long. The function modpow also reduces \(a\) modulo \(10^9 + 7\) before it multiplies.
For \(b = 0\) the function returns \(1\), which also gives \(0^0 = 1\).
#include <iostream>
using namespace std;
const long long MOD = 1'000'000'007;
long long modpow(long long a, long long b, long long m) {
if (b == 0) return 1;
long long half = modpow(a, b / 2, m);
long long res = (half * half) % m;
if (b % 2 == 1) { // If b is odd
res = (res * (a % m)) % m;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
long long a, b;
cin >> a >> b;
cout << modpow(a, b, MOD) << "\n";
}
}