A^B mod C#1121

A^B mod C (Editorial)

Problem

Given integers $a$ , $b$ , and $c$ , compute: [ a^b c ] for multiple test cases. Constraints: $1 \leq a, b, c < 2^{63}$ 1 \le a, b, c < 2^{63}.

—

General Idea:

Directly computing $a^{b}$ a^b is impossible for large $b$ due to overflow. Instead, we use **modular exponentiation** (also called fast exponentiation) which calculates: [ (a^b) c ] efficiently in $O (lo g b)$ \mathcal{O}(\log b) time.

—

Algorithm:

Initialize $r es u l t = 1$ result = 1.
While $b > 0$ b > 0:
- If $b$ is odd, multiply $r es u l t$ by $a$ modulo $c$ .
- Square $a$ modulo $c$ .
- Divide $b$ by $2$ (right shift).
Return $r es u l t$ .

This approach avoids overflow by taking modulo at every multiplication. For very large numbers, we can use '__int128_t' in C++ to handle intermediate multiplication safely.

—

Time Complexity: $O (lo g b)$ \mathcal{O}(\log b) per test case. Memory Complexity: $O (1)$ .

—

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;

int64 modPow(int64 a, int64 b, int64 mod) {
    a %= mod;
    int64 result = 1 % mod;

    while (b > 0) {
        if (b & 1)
            result = (i128)result * a % mod;
        a = (i128)a * a % mod;
        b >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int64 a, b, c;
    while (cin >> a >> b >> c) {
        cout << modPow(a, b, c) << "\n";
    }
    return 0;
}

C++