14. Modulo and its theorems

The % operator has been used since Chapter 03 to check odd or even. This chapter treats it as a mathematical tool: its properties, how to use it on huge numbers, and two theorems that often appear in OSN problems.

Remainder

a % m is the remainder when a is divided by m. For positive a and m, the result is always between 0 and m − 1.

cout << 17 % 5 << "\n";     // 2
cout << 20 % 5 << "\n";     // 0
cout << 3 % 5 << "\n";      // 3

Two numbers are called congruent modulo m if their remainders are equal:

17 ≡ 2 (mod 5), because both have remainder 2.

How to read it: modulo splits all integers into m groups. In modulo 5, the numbers 2, 7, 12, 17, and 22 are in the same group.

The most helpful picture is a clock. A wall clock works modulo 12: 10 o'clock plus 5 hours is 3 o'clock, not 15 o'clock, because 15 mod 12 = 3. All the modulo properties below are really properties you have been using since childhood when reading a clock:

int mod_benar(int a, int m) {
    return ((a % m) + m) % m;
}

Properties of modulo

This is why modulo is so useful: it "passes through" addition, subtraction, and multiplication.

The reason is easy to see for addition. Write a = q·m + r₁ and b = p·m + r₂. Then:

a + b = (q + p)·m + (r₁ + r₂)

The part (q + p)·m is divisible by m, so it contributes nothing to the remainder. What is left is only r₁ + r₂, the sum of the two remainders. The same holds for multiplication, because every term of the product except r₁ · r₂ contains the factor m.

This means you may take the remainder at any point in the middle of the computation without changing the final answer. This is what lets a program answer problems like "what is 2¹⁰⁰⁰ mod 1,000,000,007" without ever storing a thousand-digit number.

Why 1,000,000,007

Problems often ask for the answer "modulo 10⁹ + 7". The reasons:

• The actual answer is too large to store (it can have thousands of digits).
• 10⁹ + 7 is a prime number, which makes modular division possible using Fermat's theorem.
• The product of two numbers below 10⁹ + 7 still fits in long long (about 10¹⁸ < 9.2 × 10¹⁸).

The writing pattern:

const long long MOD = 1000000007;

long long hasil = 1;
for (int i = 1; i <= n; i++) {
    hasil = hasil * i % MOD;        // take the remainder every time
}

Trace it for n = 5 with MOD = 7, so the numbers are small and easy to check:

Check: 5! = 120, and 120 = 17 × 7 + 1, so 120 mod 7 is indeed 1. Notice that the intermediate values never exceed 24 even though the actual answer is 120 — and in a real problem, that is the difference between a number that fits in long long and a number with a million digits.

Fast modular exponentiation

Computing aᵇ mod m with a loop of b iterations needs O(b) steps — impossible for b = 10¹⁸. It is sped up by splitting the exponent:

• if b is even: aᵇ = (aᵇ⁄²)²
• if b is odd: aᵇ = a × aᵇ⁻¹

Each step halves b, so the number of steps is O(log b). For b = 10¹⁸ that is about 60 steps.

How it works can be read from the binary form of the exponent. Since 5 = 101 in binary, meaning 5 = 4 + 1, we get:

a⁵ = a⁴ · a¹

The loop below checks the bits of b one by one from the right. The variable a keeps getting squared so it successively holds a¹, a², a⁴, a⁸, …, and it is only multiplied into hasil when the corresponding bit is set.

long long pangkat_mod(long long a, long long b, long long m) {
    long long hasil = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) hasil = hasil * a % m;
        a = a * a % m;
        b /= 2;
    }
    return hasil;
}

Trace pangkat_mod(3, 5, 1000):

Correct: 3⁵ = 243.

Read it together with the binary form from before: the set bits in 5 = 101₂ are bit 0 and bit 2, so what gets multiplied into hasil is a¹ = 3 and a⁴ = 81. The result is 3 × 81 = 243.

Fermat's little theorem

If p is a prime number and a is not divisible by p, then aᵖ⁻¹ ≡ 1 (mod p).

Example: p = 7, a = 3 → 3⁶ = 729 = 104 × 7 + 1, so 729 ≡ 1 (mod 7).

It has two uses in OSN.

1. Shortening huge exponents. Since aᵖ⁻¹ ≡ 1, the exponent can be taken modulo p − 1:

a^b mod p = a^(b mod (p−1)) mod p, provided a is not divisible by p.

2. Modular division. Multiply both sides by a⁻¹:

a⁻¹ ≡ aᵖ⁻² (mod p)

So dividing by a in the modulo p world is the same as multiplying by pangkat_mod(a, p - 2, p).

long long invers(long long a, long long p) {
    return pangkat_mod(a, p - 2, p);        // only if p is prime
}

// (x / y) mod p
long long bagi_mod(long long x, long long y, long long p) {
    return x % p * invers(y, p) % p;
}

This is what lets the combination formula (Chapter 17) be computed modulo 10⁹ + 7, even though the formula contains division of factorials.

Problem patterns that use modulo

Last digit. The units digit of a number is its value mod 10. The last digit of 7¹⁰⁰ is pangkat_mod(7, 100, 10).

Cycles and clocks. Day n counting from Monday is n % 7. The clock hand after n hours is (sekarang + n) % 12 (sekarang = "now").

Divisibility tests. A number is divisible by 3 (or 9) if the sum of its digits is divisible by 3 (or 9). The reason: 10 ≡ 1 (mod 9), so every digit contributes its own value.

Avoiding overflow. Problems with large answers almost always ask for the result modulo some number, precisely so that it can be computed.

Homework

Most common mistakes

OSN tips

The sentence "output the answer modulo 1,000,000,007" means the answer is very large. That sentence is also a hint that what is asked is to count, not to construct: a problem whose answer needs a remainder is almost always a combinatorics or DP problem with an exploding number of ways.

Take the remainder at every step, not at the end. Delaying % MOD until the last line makes the accumulator overflow long before it gets there. The practical rule: every time there is a + or * on values that are already reduced, immediately follow it with % MOD.

Multiplying two remainders needs long long. Two numbers below 10⁹ + 7 multiplied together reach about 10¹⁸ — more than four hundred million times beyond int, and still fitting in long long. This is why the modulus is chosen that large but no larger.

% in C++ can give a negative result. -7 % 3 is -1, not 2. If there is subtraction or negative data, wrap it in the standard pattern:

hasil = ((a - b) % MOD + MOD) % MOD;

This mistake does not show up in sample tests that are entirely positive, and only appears as Wrong Answer on the test files.

Division does not exist in the modulo world. (a / b) % MOD is almost always wrong. The correct way is to multiply by the modular inverse, and for a prime modulus the inverse is computed with pangkat(b, MOD - 2). Every time division appears in a formula — for example in the combination formula — think inverse.

An exponent that is too large is reduced modulo MOD − 1. Fermat's little theorem gives a^(p−1) ≡ 1 (mod p) for prime p and a not a multiple of p. Note the different moduli: the base is taken modulo p, the exponent modulo p − 1. Mixing them up is a very common mistake.

Summary

• a % m is the remainder; for positive a and m the result is 0 to m − 1. For negative a, C++ gives a negative result — fix it with ((a % m) + m) % m.
• Modulo "passes through" addition, subtraction, and multiplication, so the remainder may be taken at any point in the middle of a computation.
• Modulo does not pass through division; division is done with the modular inverse.
• 10⁹ + 7 is chosen because it is prime and because the product of two numbers below it still fits in long long.
• Fast modular exponentiation needs O(log b) steps by splitting the exponent into its binary form.
• Fermat's little theorem: for prime p and a not divisible by p, aᵖ⁻¹ ≡ 1 (mod p). As a consequence, the inverse of a is pangkat_mod(a, p - 2, p).

OSN-style exercises

The following three problems use three different tools from this chapter: fast modular exponentiation, Fermat's little theorem, and the remainder property of prefix sums.

Skeletons for all three are in exercises/14/osn/.

Problem 1 — Power Series Remainder

Compute 1^K + 2^K + … + N^K, then output its remainder when divided by 1,000,000,007.

Input format. One line containing two integers N and K.

Output format. One line containing the remainder of that sum.

Constraints.

• 1 ≤ N ≤ 10⁶
• 1 ≤ K ≤ 10⁹

Sample input

3 2

Sample output

14

Explanation. 1² + 2² + 3² = 1 + 4 + 9 = 14, and 14 is smaller than the modulus, so the remainder stays 14. Note how large K is: computing i^K by multiplying K times is clearly impossible.

Skeleton: exercises/14/osn/01-deret-pangkat.cpp

Problem 2 — Tower of Powers

Compute A to the power (B to the power C), then output its remainder when divided by 1,000,000,007.

Input format. One line containing three integers A, B, and C.

Output format. One line containing the remainder.

Constraints. 1 ≤ A, B, C ≤ 10⁹. Note that A is always smaller than 1,000,000,007, so A is never a multiple of the modulus.

Sample input

2 3 2

Sample output

512

Explanation. B^C = 3² = 9, and 2⁹ = 512. For larger inputs, B^C itself cannot be stored in any type — for example 10⁹ to the power 10⁹ has about nine billion digits. So the exponent must be reduced first, and the condition on A above is what makes that valid.

Skeleton: exercises/14/osn/02-pangkat-bertingkat.cpp

Problem 3 — Subarrays Divisible by K

Given a sequence of N integers. Count how many non-empty contiguous subarrays have a sum divisible by K.

Input format. The first line contains two integers N and K. The second line contains N integers.

Output format. One line containing the number of subarrays.

Constraints.

• 1 ≤ N ≤ 200,000
• 1 ≤ K ≤ 10⁶
• −10⁹ ≤ Aᵢ ≤ 10⁹

Sample input

5 3
1 2 3 4 1

Sample output

4

Explanation. The subarrays are 2 3 4 (sum 9), 3 (sum 3), 1 2 3 (sum 6), and 1 2 (sum 3). Negative numbers may also appear in the test files, and % in C++ gives a negative remainder for negative numbers — that is part of the problem.

Skeleton: exercises/14/osn/03-subarray-habis-dibagi.cpp

Stuck or already done? Open the homework solutions page.