14. Modulo and its theorems — Homework Solutions

The answer .cpp files are in exercises/14/homework/solutions/.

Open this page after trying on your own. Compare your line of reasoning with the How to think about it section, not the code line by line: two pieces of code with different shapes can both be correct, and what is worth copying is how to get there. The Test part of each problem contains inputs and outputs that have already been checked — run your own answer on those inputs before considering yourself done.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/14/homework/solutions/01-mod-benar.cpp
./jawab

Problem 1 — Correct modulo

Problem. A remainder that is always between 0 and m − 1, including for negative a.

How to think about it. a % m in C++ can be negative. Adding m once is enough to make it positive, because a % m is never smaller than −(m − 1). The final % m brings it back into range if the addition made the value reach m.

Walkthrough.

cout << ((a % m) + m) % m << "\n";

Tests.

The third row is the form you will meet often: the result of a modular subtraction that falls to -1 must be brought back to MOD - 1, not left negative.

Common mistakes.

• Writing if (a < 0) a = -a;. That changes the problem: −7 mod 3 is not 7 mod 3.
• Adding m without the final % m, so a = 0 gives the answer m, not 0.

Problem 2 — Factorial modulo

Problem. n! mod 10⁹ + 7 for n up to one million.

How to think about it. 1,000,000! has more than five million digits — impossible to store. The multiplication property of modulo saves it: take the remainder at every multiplication step, not at the end.

Walkthrough.

long long hasil = 1;
for (int i = 2; i <= n; i++) hasil = hasil * i % MOD;
cout << hasil << "\n";

For n = 10 the result is 3,628,800 (still below MOD, so it appears in full); for n = 1,000,000 the result is 641,102,369.

Tests.

The third row is a good check: 20! still fits in long long, so you can compute it without modulo, then take the remainder yourself to compare. From 21! on, that approach can no longer be used.

Common mistakes.

• Storing hasil as int. hasil * i overflows immediately.
• Taking the modulo only once at the end. The intermediate values are already corrupted long before that.
• Using double to hold a large factorial. double loses precision after about 15 digits.

Problem 3 — Fast modular exponentiation

Problem. aᵇ mod m with b up to 10¹⁸.

How to think about it. The key to the speedup: each step halves b, while squaring a. If the lowest bit of b is set, the current a is also multiplied into the result.

The line a %= m; at the start matters for a larger than m.

Walkthrough.

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;
}

Check: 2 10 1000 gives 24 (2¹⁰ = 1024), and 3 0 7 gives 1 — a zero exponent always gives 1.

Tests.

The third row is the reason this whole function exists: the exponent is 10¹⁸, and the answer still appears instantly because only about 60 squarings are performed.

Common mistakes.

• Using a loop of b iterations. For b = 10¹⁸ the program will never finish.
• Writing int for a or hasil. a * a with a close to 10⁹ needs long long.
• Forgetting that for m = 1 the answer is always 0; the formula above already handles it because hasil * a % 1 is always 0.

Problem 4 — Divisibility by 9 test

Problem. A number of up to 100,000 digits, divisible by 9 or not.

How to think about it. The number does not fit in any type, so it is read as a string. The property used: 10 ≡ 1 (mod 9), so 10ᵏ ≡ 1 for every k. This means every digit contributes its own value, and the number is congruent to the sum of its digits modulo 9.

A digit character is turned into a number with s[i] - '0'.

Walkthrough.

string s;
cin >> s;

long long jumlah = 0;
for (int i = 0; i < (int)s.size(); i++) jumlah += s[i] - '0';

if (jumlah % 9 == 0) cout << "YA\n";
else cout << "TIDAK\n";

Tests.

The third row is the core of the problem: that 24-digit number does not fit in long long at all, but its digit sum can be computed as long as the number is read as a string. This is the general pattern for "very long number" problems.

Common mistakes.

• Trying long long n; cin >> n; for a 100,000-digit number.
• Adding s[i] without - '0', so what gets added is the character codes (48 to 57).
• Using this rule for divisors other than 3 and 9. For 11 the rule is different (alternating digit sum), because 10 ≡ −1 (mod 11).

Challenge — Modular inverse

Problem. (x / y) mod p with prime p.

How to think about it. Division does not have the modulo property. What is used is the inverse: the number y⁻¹ satisfying y × y⁻¹ ≡ 1 (mod p). Fermat's little theorem gives it directly: y⁻¹ ≡ yᵖ⁻² (mod p).

Once the inverse is found, division becomes multiplication:

(x / y) mod p = x × y^(p−2) mod p

The check at the end is a good habit: multiply the result back by y; if it is correct, the result comes back to x mod p.

Walkthrough.

long long invers(long long a, long long p) {
    return pangkat_mod(a, p - 2, p);
}

long long hasil = x % p * invers(y, p) % p;
cout << hasil << "\n";
cout << hasil * (y % p) % p << "\n";

For 10 3 1000000007, the result is 333,333,339 — and 333,333,339 × 3 mod 10⁹ + 7 = 10, as expected.

Tests.

That second check line is the habit worth copying: after dividing modularly, multiply the result back by the denominator and make sure it returns to the original value. A check that short catches almost all modular inverse mistakes.

Common mistakes.

• Using this formula for a p that is not prime. Fermat's little theorem does not apply; what is needed is the extended Euclidean algorithm (Chapter 15).
• Looking for the inverse of a y that is divisible by p. That inverse does not exist, and the formula gives a meaningless answer.
• Writing x / y % p with ordinary integer division. For x = 10, y = 3 that gives 3 — an entirely different answer.

OSN-style exercises — walkthrough

The answer files are in exercises/14/osn/solutions/.

Problem 1 — Power Series Remainder

How to think about it. There are N terms, and each term is a power with an exponent up to 10⁹. Computing one term by multiplying K times means 10⁶ × 10⁹ = 10¹⁵ multiplications. Fast modular exponentiation brings that down to about 30 multiplications per term, so the total is about 3 × 10⁷ — it fits. Measured on the author's machine, N = 10⁶ and K = 10⁹ finishes in 0.18 seconds.

Walkthrough.

const long long MOD = 1000000007LL;

long long pangkat(long long alas, long long eksponen) {
    long long hasil = 1;
    alas %= MOD;
    while (eksponen > 0) {
        if (eksponen % 2 == 1) hasil = hasil * alas % MOD;
        alas = alas * alas % MOD;
        eksponen /= 2;
    }
    return hasil;
}

// ...
long long total = 0;
for (long long i = 1; i <= n; i++) {
    total = (total + pangkat(i, k)) % MOD;
}

The line alas %= MOD (alas = "base") at the start of the function is not decoration: it guarantees the function stays correct even when called with a base larger than the modulus.

Tests.

Common mistakes.

• Computing the power with a loop of K iterations.
• Summing all the terms first and only then taking the remainder. The accumulator overflows long before it finishes.
• Using int inside the power function, so alas * alas overflows.

Problem 2 — Tower of Powers

How to think about it. The exponent, B^C, cannot be computed at all — for B = C = 10⁹ the number has about nine billion digits. So what gets reduced is not the result, but the exponent.

Fermat's little theorem states a^(p−1) ≡ 1 (mod p) for prime p and a not a multiple of p. As a consequence, powers of a repeat with period p − 1, so

a^e ≡ a^(e mod (p−1))  (mod p)

So the steps are two fast modular exponentiations with different moduli: first B^C mod (p − 1) to get the exponent, then A to that exponent mod p.

The condition "A is not a multiple of p" is guaranteed by the constraint A ≤ 10⁹, which is smaller than p = 1,000,000,007. Without that guarantee, this step is not valid — and OSN problems that use this technique almost always include a similar constraint.

Walkthrough.

long long eksponen = pangkat(b, c, MOD - 1);
cout << pangkat(a, eksponen, MOD) << "\n";

Since it is used with two moduli, the power function takes the modulus as a parameter.

Tests.

Common mistakes.

• Computing b * c as the exponent. That is A^(B×C), a different problem.
• Reducing the exponent modulo MOD instead of MOD − 1.
• Using pangkat(b, c, MOD) for the exponent — the moduli are swapped, and the result is wrong without any symptom.

Problem 3 — Subarrays Divisible by K

How to think about it. The sum of the subarray A_l through A_r equals pre[r] − pre[l−1], as in Chapter 10. That sum is divisible by K exactly when pre[r] and pre[l−1] have the same remainder when divided by K.

So the problem changes shape: count how many pairs of prefixes have the same remainder. That can be done in a single pass with a counter array of length K: when a new remainder is computed, add the number of earlier prefixes with the same remainder, then record this prefix.

The empty prefix — before the first element — must also be counted, because it represents subarrays that start at the first element. That is why cacah[0] ("count") is set to 1 before the loop.

Negative numbers. % in C++ follows the sign of the dividend, so the remainder can be negative and immediately become an out-of-bounds array index. The pattern ((x % k) + k) % k fixes it.

Walkthrough.

vector<long long> cacah(k, 0);
cacah[0] = 1;                       // empty prefix

long long sisa = 0, hasil = 0;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;

    sisa = ((sisa + x) % k + k) % k;    // stays non-negative
    hasil += cacah[sisa];
    cacah[sisa]++;
}

Notice that sisa ("remainder") never stores the actual sum, only its remainder. The actual sum can reach 2 × 10¹⁴ and is not needed.

The number of subarrays in the worst case — 200,000 numbers that are all multiples of K — reaches about 2 × 10¹⁰, so hasil must be long long.

Tests.

The second case is the check for cacah[0] = 1: with four numbers, all 4 × 5 / 2 = 10 subarrays are divisible by 2. An answer of 6 means the empty prefix was not counted.

Common mistakes.

• Forgetting cacah[0] = 1, so all subarrays starting at the first element are not counted.
• Using sisa = (sisa + x) % k without the sign adjustment, so the program reads cacah[-2] and ends in a Runtime Error or a random answer.
• Storing the actual prefix sums and then comparing them pairwise. Correct, but N² = 4 × 10¹⁰.

If you are still stuck

• The modulo result becomes negative → Chapter 14, section Remainder and the function mod_benar.
• The answer overflows even though it is already reduced → check the data type: the product of two numbers below 10⁹ + 7 must be computed as long long.
• Modular division gives a nonsensical number → Chapter 14, section Fermat's little theorem; division is done with the inverse.

The two tools of this chapter — fast modular exponentiation and the modular inverse — are used again in Chapter 17 to compute combinations.