Exponentiation

Exponentiation
CSES easy

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";
    }
}