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 % Mis 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?
- It fits in an
int: 1000000007 < 2147483647 (2^31 − 1). - 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. - 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 & 1is the lowest bit of b (1 if b is odd).b >>= 1shifts b right, dropping that bit (episode 17).- Both
r * aanda * amultiply two values below M, so they fit inlong 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
-
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. -
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. -
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). -
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. -
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
- 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
intkeeps every product insidelong longand allows division via inverses. - What is the time complexity of binary exponentiation? O(log b) multiplications; each one is O(1) for 64-bit values.
- Why must
abe reduced before the loop? a can be up to 10^18;a * awould overflow before any% M. - How do you get a non-negative remainder in C++?
((x % M) + M) % M, because%keeps the sign of the dividend. - 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.
- What if M is around 10^18? Then
a * aoverflowslong 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% Mat every step; division does not (episode 22). - 10^9 + 7 fits in an
int, products of two remainders fit inlong 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 %= Mfirst, multiply inlong 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.