Understanding Modular Exponentiation (modPow) for Beginners

Learn how to compute ab mod m efficiently using the binary exponentiation method in C++. A must-know technique for competitive programming and cryptography.

The modPow Function

long long modPow(long long a, long long b, long long m) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

What Does It Do?

This function calculates a^b mod m efficiently. Instead of multiplying a by itself b times, it uses binary exponentiation, which breaks the exponent into bits.

Step-by-Step Example

Let's compute 3¹³ mod 17:

Binary of 13 → 1101
Start: res = 1, a = 3, b = 13
Bit is 1 → res = 3
Square a → 9, shift b → 6
Bit is 0 → res stays 3
Square a → 13, shift b → 3
Bit is 1 → res = 5
Square a → 16, shift b → 1
Bit is 1 → res = 12

Final result: 12

Why Is This Fast?

Instead of O(b) multiplications, this method only needs O(log b). That means even for very large b, the calculation is quick.

Common Uses

Fast power calculation in competitive programming
Finding modular inverses when m is prime
Cryptography algorithms like RSA

Pitfalls to Avoid

Using normal division instead of modular inverse when dividing under mod
Forgetting to handle negative numbers by adjusting with (x % m + m) % m
Not using a big enough data type for intermediate multiplications

Modular Division Using Fermat’s Little Theorem

In modular arithmetic, division is not the same as in regular arithmetic. If we want to compute x / y mod M (where M is prime and y is not divisible by M), we actually multiply by the modular inverse of y.

The math proof

Let M be prime. Fermat’s Little Theorem says:

y^M-1 ≡ 1 (mod M) for gcd(y, M) = 1

Multiplying both sides by y^-1 gives:

y^M-2 ≡ y^-1 (mod M)

This means:

(x / y) mod M ≡ x · y^M-2 mod M

We can compute y^M-2 efficiently using binary exponentiation (the same method in modPow).

Example

Suppose we want to compute:

(10 / 4) mod 7

M = 7 (prime), so the inverse of 4 is 4^7-2 mod 7 = 4⁵ mod 7.
Using fast exponentiation: 4² ≡ 2 (mod 7) → 4⁴ ≡ 4 (mod 7) → 4⁵ ≡ 2 (mod 7). So 4^-1 ≡ 2.
Now: (10 / 4) mod 7 ≡ 10 × 2 mod 7 ≡ 20 mod 7 ≡ 6.

Therefore, (10 / 4) mod 7 = 6.

In code

long long divideMod(long long x, long long y, long long M) {
    return (x * modPow(y, M - 2, M)) % M;
}

This function works only when M is prime and gcd(y, M) = 1. The modPow function is our fast exponentiation routine.

Range Product Queries of Powers | LeetCode

This problem asks you to represent a given number n as the sum of distinct powers of two. Then, for each query [l, r], you must compute the product of the subset of powers of two from index l to r, taken modulo 10⁹+7.

Example

Suppose n = 13 → binary: 1101 → powers: [1, 4, 8] (2⁰, 2², 2³).
Query [0, 1] → product = 1 × 4 = 4.

Efficient solutions use prefix products and modular inverses to quickly compute results without recalculating each product from scratch.

class Solution {
public:
    const int mod = 1e9+7;

    long long modPow(long long a, long long b, long long m) {
        long long res = 1;
        while (b > 0) {
            if (b & 1) res = (res * a) % m;
            a = (a * a) % m;
            b >>= 1;
        }
        return res;
    }
      

    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int>v;
        for(int i = 0; i<32; i++){
            if(n&(1LL<<i))v.push_back(1LL<<i);
        }
        vector<long long>pre;
        pre.push_back(v[0]);
        for(int i = 1; i<v.size(); i++){
            pre.push_back(1LL*(pre[i-1]*v[i]));
            pre[i] = (pre[i]+mod)%mod;
        }
        vector<int>ans;
        for(int i = 0; i<queries.size(); i++){
            int left = queries[i][0], right = queries[i][1];
            int temp = pre[right];
            if(left>0)temp = (temp * modPow(pre[left - 1], mod - 2, mod)) % mod;
            ans.push_back((temp+mod)%mod);
        }
        return ans;
    }
};

Explanation | Range Product Queries of Powers

The problem asks us to express an integer n as a sum of distinct powers of two (based on its binary representation).
We store these powers of two in an array v in increasing order.
We build a prefix product array pre, where each element stores the product of all powers of two up to that index, modulo 10⁹ + 7.
For each query [left, right], we want the product of elements from v[left] to v[right], modulo mod.
Instead of recalculating products for each query, we use the formula:
```
product = pre[right] × inverse(pre[left - 1]) mod M
```
The modular inverse is computed using Fermat’s Little Theorem:
```
inverse(a) = a^(mod-2) mod mod
```
which is implemented with fast exponentiation (modPow).
This approach ensures each query is answered in O(log mod) time after the initial O(32) preprocessing of powers.
The time complexity is efficient: preprocessing takes constant time for powers of two (since n fits in 32 bits) and each query is logarithmic due to modular exponentiation.