SyntaxPilot
Courses/Competitive Programming/Lesson 21

Competitive Programming · Lesson 21 of 90 · 11 min

Modular arithmetic and fast exponentiation

queued

These are the notes for Competitive Programming episode 21 (number theory 3). Episode 20 sieved millions of primes. Today is about the sentence you will read in a huge number of contest problems: "print the answer modulo 10^9 + 7". We start from counting phone-lock combinations, watch a^b overflow long long silently, fix it with the wall clock (modular arithmetic), see why everyone picks 10^9 + 7, and then meet an original problem, Lock Combos, where multiplying b times gets Time Limit Exceeded for b = 10^18. Folding a sheet of paper leads to binary exponentiation (fast power): a^b in about 60 steps. A stress test confirms it, and three real bugs close the episode. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hooks

Phone-lock combinations. A 4-digit PIN has 10 choices per digit, so 10 · 10 · 10 · 10 = 10^4 = 10000 PINs. A lock with b positions and a symbols on each has a^b combinations. With 30 positions that is 10^30, far beyond the largest long long (about 9.2 · 10^18).

The wall clock. It is 9 o'clock and your train is 5 hours late. 9 + 5 = 14, but the clock shows 2: it wrapped past 12. The clock only keeps the remainder after dividing by 12 (14 % 12 = 2). A hundred hours later? (9 + 100) % 12 = 1, without counting a hundred ticks. The numbers on a clock never grow. That is modular arithmetic, and the size of the clock is the modulus M.

Folding paper. Fold a sheet in half: 2 layers. Again: 4, then 8, then 16. Each fold doubles everything you already have. Ten folds, ten moves: 2^10 = 1024 layers. Squaring instead of multiplying one at a time is the heart of fast power.

Overflow is silent

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

int main() {
    ll a, b;
    cin >> a >> b;
    ll r = 1;
    for (ll i = 0; i < b; i++)
        r = r * a;
    cout << r << "\n";
    return 0;
}
Input Output
10 4 10000
10 30 5076944270305263616

10 30 is not 10^30, and there is no error message. Signed overflow in C++ is undefined behaviour; in practice the value wraps around and you get a silent Wrong Answer. (5076944270305263616 is exactly 10^30 mod 2^64.)

Modular arithmetic: the rules

  • x % M is the remainder of x divided by M: a number from 0 to M − 1. 17 % 7 = 3.
  • Addition: (a + b) % M == (a % M + b % M) % M
  • Multiplication: (a · b) % M == (a % M) · (b % M) % M
  • Subtraction: (a − b) % M == (a % M − b % M) % M, but C++'s % keeps the sign of the left side, so the result can be negative. Fix: ((a - b) % M + M) % M.
  • Division does not work this way. That is episode 22 (modular inverse).

Check with M = 7: 12 · 13 = 156 and 156 % 7 = 2. Reducing first: (12 % 7) · (13 % 7) = 5 · 6 = 30, and 30 % 7 = 2. Same remainder.

So you may take % M after every addition and multiplication, and the numbers stay below M forever.

Why 10^9 + 7?

  1. It fits in an int: 1000000007 < 2147483647 (2^31 − 1).
  2. Products fit in a long long: two remainders are below 10^9 + 7, so their product is below about 1.0000000140 · 10^18 < 9.2 · 10^18.
  3. It is prime, which makes division possible (Fermat's little theorem, episode 22).

The consequence: even when both values fit in an int, their product does not (10^9 · 10^9 = 10^18). Multiply in long long. Another common modulus is 998244353, also prime, also below 2^30.

Problem V · Lock Combos

Original problem written for this course, in the style of a Div. 2 A/B.

You are given t test cases. Each has two integers a and b. Print a^b modulo 10^9 + 7. (0^0 is defined as 1.)

Constraints: 1 ≤ t ≤ 10^5, 0 ≤ a ≤ 10^18, 0 ≤ b ≤ 10^18. Time limit 2 seconds.

Sample input

3
10 4
10 30
2 100

Sample output

10000
999657007
976371285

Brute force: multiply b times (Time Limit Exceeded)

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

const ll M = 1000000007;

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll a, b;
        cin >> a >> b;
        a %= M;
        ll r = 1;
        for (ll i = 0; i < b; i++)
            r = r * a % M;
        cout << r << "\n";
    }
    return 0;
}

On the sample it prints 10000, 999657007, 976371285: correct, no overflow. On 1 / 2 1000000000000000000 it gets Time Limit Exceeded: the loop runs b = 10^18 times. At 10^9 simple steps per second that is about 32 years.

Binary exponentiation (fast power)

Squaring doubles the exponent: a^(2k) = a^k · a^k. So a, a², a⁴, a⁸, … each take one multiplication.

Any b is a sum of powers of two: its binary digits. 13 = 1101₂ = 8 + 4 + 1, so

a^13 = a^8 · a^4 · a^1.

Walk through the bits of b from the lowest: keep a running square (a, a², a⁴, …), and whenever the current bit is 1, multiply the answer by the current square. b has at most 60 bits for b ≤ 10^18, so this is about 60 squarings and at most 60 multiplications: O(log b).

Step b (binary) lowest bit r a (current square)
start 1101 1 1 → a a → a²
2 110 0 a a² → a⁴
3 11 1 a · a⁴ a⁴ → a⁸
4 1 1 a · a⁴ · a⁸ = a^13 a⁸ → a^16
end 0 a^13

The accepted solution

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

const ll M = 1000000007;

ll power(ll a, ll b) {
    ll r = 1;
    a %= M;
    while (b > 0) {
        if (b & 1) r = r * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll a, b;
        cin >> a >> b;
        cout << power(a, b) << "\n";
    }
    return 0;
}
Input Output Why
the sample 10000 / 999657007 / 976371285 same as the brute force
1 / 2 1000000000000000000 719476260 instant: 60 steps
5 0 1 b = 0: the loop never runs, r stays 1
1000000007 5 0 a ≡ 0 (mod M)
1000000000000000000 1000000000000000000 504853526 both at the limit
1000000000000000000 2 2401 10^18 ≡ 49 (mod M), 49² = 2401
  • b & 1 is the lowest bit of b (1 if b is odd). b >>= 1 shifts b right, dropping that bit (episode 17).
  • Both r * a and a * a multiply two values below M, so they fit in long long.

Stress test: slow vs fast

As in episode 5: compare the trusted slow loop with the fast one on many random inputs where the slow one is still quick.

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

const ll M = 1000000007;

ll power(ll a, ll b) {
    ll r = 1;
    a %= M;
    while (b > 0) {
        if (b & 1) r = r * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return r;
}

int main() {
    mt19937 rng(21);
    for (int it = 1; it <= 100000; it++) {
        ll a = rng() % 2000000000, b = rng() % 300;
        ll slow = 1;
        for (ll i = 0; i < b; i++) slow = slow * (a % M) % M;
        if (slow != power(a, b)) {
            cout << "MISMATCH " << a << " " << b << "\n";
            return 0;
        }
    }
    cout << "all 100000 tests match\n";
    return 0;
}

Output: all 100000 tests match.

Complexity vs the constraints

Approach Time per test t = 10^5, b = 10^18 Verdict
Multiply b times, no mod O(b) overflow long before Wrong Answer
Multiply b times, % M O(b) 10^18 per test Time Limit Exceeded
Fast power O(log b) ≈ 60 10^5 · 60 = 6 · 10^6 Accepted

Memory is O(1) in every version.

Common mistakes (and the real outputs)

Bug 1: forgetting a %= M

Remove the a %= M; line from power and run 1 / 1000000000000000000 2. Expected 2401; real output 673529572. With b = 2 the first bit is 0, so the first operation is a * a with a = 10^18: that is 10^36, which overflows before the % M.

Bug 2: int instead of long long

const int M = 1000000007;
int power(int a, int b) {
    int r = 1;
    a %= M;
    while (b > 0) {
        if (b & 1) r = r * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return r;
}

On the sample: 10000, -702005248, 0. As soon as a passes about 46341, a * a exceeds 2^31 − 1 and overflows.

Bug 3: a negative remainder after subtraction

ll x = power(3, 100);
ll y = power(2, 100);
cout << x << " " << y << "\n";     // 886041711 976371285
cout << (x - y) % M << "\n";       // -90329574

3^100 − 2^100 is positive, but after reducing, x < y, and C++ % keeps the sign of the left operand. Fix: ((x - y) % M + M) % M prints 909670433, the correct value.

Summary table

Mistake Real output Why Fix
r = r * a; with no mod 5076944270305263616 for 10^30 overflow, silently % M after every multiplication
power without a %= M 673529572 (expected 2401) a * a = 10^36 reduce a first
int power(int a, int b) -702005248, 0 a * a > 2^31 − 1 long long everywhere
(x - y) % M -90329574 % keeps the sign ((x - y) % M + M) % M
loop b times Time Limit Exceeded O(b) with b = 10^18 fast power, O(log b)

Mini project

Write a tiny "mod calculator" that reads lines like add 5 7, mul 123456789 987654321, sub 3 10, pow 2 1000000000000000000 and prints each result mod 10^9 + 7, always in 0 … M − 1. Then add pow with a modulus given on the line (powm 7 222 1000) and check it against Python's pow(a, b, m).

Practice

  1. n-digit strings with no zero. How many strings of n digits use only 1–9? Print mod 10^9 + 7, n ≤ 10^18.

    Solution Each position has 9 choices: the answer is 9^n mod M, computed with <code>power(9, n)</code>. For n = 3: 729.

  2. Many powers of two. t ≤ 10^5 queries, each n ≤ 10^18: print 2^n mod 10^9 + 7.

    Solution Fast power per query: 10^5 · 60 steps. Use fast I/O. n = 100 gives 976371285.

  3. Last three digits. Print the last three digits of 7^(10^18) (with leading zeros).

    Solution The last three digits are the remainder mod 1000, so run fast power with M = 1000 and print with <code>printf("%03lld")</code>. The answer is <code>001</code> (7^20 ≡ 1 mod 1000 and 20 divides 10^18).

  4. Sum 1 + 2 + … + n mod M, n ≤ 10^18.

    Solution The formula n(n + 1)/2 overflows and needs division. Divide first: if n is even use (n/2 % M) · ((n + 1) % M) % M, otherwise (n % M) · ((n + 1)/2 % M) % M. For n = 10^18 the answer is 1225. In episode 22 you'll do the same with the modular inverse of 2.

  5. Power tower check. Without running code, how many multiplications does fast power do for b = 1023? For b = 1024?

    Solution 1023 = 1111111111₂: 10 squarings and 10 multiplications into r. 1024 = 10000000000₂: 11 squarings and 1 multiplication.

Quick quiz

Fast power computes 3^11. Which squares does it multiply into r?

A) 3^8 · 3^2 · 3^1 B) 3^8 · 3^3 C) 3^4 · 3^4 · 3^2 · 3^1 D) 3^8 · 3^4 · 3^1

Answer

A. 11 = 1011₂ = 8 + 2 + 1. D would be 3^13, and 3^3 in B is not one of the squares (a, a², a⁴, a⁸).

Interview questions

  1. Why do contest problems ask for the answer modulo 10^9 + 7? The true answer is too big for 64-bit integers; a prime modulus that fits in an int keeps every product inside long long and allows division via inverses.
  2. What is the time complexity of binary exponentiation? O(log b) multiplications; each one is O(1) for 64-bit values.
  3. Why must a be reduced before the loop? a can be up to 10^18; a * a would overflow before any % M.
  4. How do you get a non-negative remainder in C++? ((x % M) + M) % M, because % keeps the sign of the dividend.
  5. Can you write fast power recursively? Yes: if b = 0 return 1; h = power(a, b/2); h = h·h % M; if b is odd multiply by a. Same O(log b), uses O(log b) stack.
  6. What if M is around 10^18? Then a * a overflows long long; multiply with __int128 ((__int128)a * b % M).

Glossary

Term Meaning Example
Overflow A value goes past the largest number a type can hold and wraps around 10^30 in a long long printed 5076944270305263616
long long 64-bit signed integer, up to about 9.2 · 10^18 ll r = 1;
Remainder / % What is left after division 14 % 12 = 2
Modulus (M) The number you take remainders by; the "size of the clock" M = 10^9 + 7
Modular arithmetic Doing +, −, · and keeping only remainders by M (9 + 5) % 12 = 2
"Answer modulo M" Print the true answer's remainder by M 10^30 mod M = 999657007
Prime A number with exactly two divisors 10^9 + 7 is prime
Exponent The power b in a^b in 2^100, b = 100
Binary representation Writing a number with bits (powers of two) 13 = 1101₂ = 8 + 4 + 1
Repeated squaring a → a² → a⁴ → a⁸: each step doubles the exponent 10 folds = 2^10 layers
Binary exponentiation / fast power a^b by squaring and picking the squares whose bit is 1 a^13 = a^8 · a^4 · a
b & 1 The lowest bit of b: 1 if b is odd 13 & 1 = 1
b >>= 1 Shift b right: drop its lowest bit (halve it) 13 → 6
O(log b) Steps grow with the number of digits of b, not b itself b = 10^18 → ~60 steps
Stress test Compare a slow trusted solution with a fast one on random inputs 100000 random pairs matched
Undefined behaviour Code whose result C++ does not define (like signed overflow) int product past 2^31 − 1

Summary

  • Overflow gives a silent Wrong Answer, so huge answers are printed mod M, usually 10^9 + 7.
  • Modular arithmetic is the wall clock: keep only remainders. +, − and · survive taking % M at every step; division does not (episode 22).
  • 10^9 + 7 fits in an int, products of two remainders fit in long long, and it is prime.
  • Multiplying b times is O(b): TLE for b = 10^18. Fast power squares and uses the bits of b: O(log b), about 60 steps.
  • Always a %= M first, multiply in long long, and fix negatives with ((x - y) % M + M) % M.

Solutions in C++, Java and Python

Problem V · Lock Combos

C++

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

const ll M = 1000000007;

ll power(ll a, ll b) {
    ll r = 1;
    a %= M;
    while (b > 0) {
        if (b & 1) r = r * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll a, b;
        cin >> a >> b;
        cout << power(a, b) << "\n";
    }
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static final long M = 1_000_000_007L;

    static long power(long a, long b) {
        long r = 1;
        a %= M;
        while (b > 0) {
            if ((b & 1) == 1) r = r * a % M;
            a = a * a % M;
            b >>= 1;
        }
        return r;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine().trim());
        StringBuilder out = new StringBuilder();
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            long a = Long.parseLong(st.nextToken()), b = Long.parseLong(st.nextToken());
            out.append(power(a, b)).append('\n');
        }
        System.out.print(out);
    }
}

Python

import sys

M = 10**9 + 7

def power(a, b):
    r = 1
    a %= M
    while b > 0:
        if b & 1:
            r = r * a % M
        a = a * a % M
        b >>= 1
    return r

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for i in range(t):
        a, b = int(data[1 + 2 * i]), int(data[2 + 2 * i])
        out.append(power(a, b))   # same as Python's built-in pow(a, b, M)
    print("\n".join(map(str, out)))

main()

All three print 10000, 999657007, 976371285 on the sample. In Python, the built-in pow(a, b, M) does exactly this, and Python integers never overflow, but in C++ and Java you must take care of overflow yourself.