Binary Exponentiation

Concept

Binary exponentiation computes a^b in O(log b) time instead of O(b). It works by squaring the base and halving the exponent at each step. When the exponent is odd, multiply the result by the current base. All operations are done modulo some value to prevent overflow.

When to Use

• ▸Computing large powers modulo a prime (a^b % mod)
• ▸Modular arithmetic in combinatorics problems
• ▸As a building block for modular inverse (Fermat's little theorem)
• ▸Any problem requiring fast exponentiation

Intuition

Instead of multiplying a by itself b times, observe that a^10 = (a^5)^2 and a^5 = a * (a^2)^2. Decompose the exponent into binary: process each bit. If the current bit is 1, multiply the answer by the current base. Then square the base for the next bit. This processes log2(b) bits total. Think of it as 'repeated squaring' — each step doubles the exponent we've handled.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

using ll = long long int;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    const ll mod = 1e9+7;

    while(n--){
        ll a, b;
        cin >> a >> b;

        ll ans = 1;
        while(b > 0){
            if(b % 2 == 1){
                ans = (ans * a) % mod;
            }
            a = (a * a) % mod;
            b /= 2;
        }

        cout << ans << "\n";
    }

    return 0;
}

// Sample Input:
// 3
// 2 10
// 3 5
// 7 3
//
// Sample Output:
// 1024
// 243
// 343