SyntaxPilot
Courses/Competitive Programming/Lesson 26

Competitive Programming · Lesson 26 of 90 · 15 min

Chinese remainder theorem

queued

These are the notes for Competitive Programming episode 26 (number theory). Dadi packs her Diwali laddoos in boxes of 3, 5 and 7 and counts the leftovers: 2, 3 and 2. How many laddoos are there? Answering that is the Chinese remainder theorem (CRT). We learn the words remainder, residue, mod and congruence, solve the puzzle by hand, and meet an original problem, Laddoo Boxes, where trying every number (and even jumping cleverly) gets Time Limit Exceeded. The fix is to merge two rules at a time by solving for the number of jumps with extended Euclid from episode 25. Two trains that stop every 4 and 6 days teach the two traps of non-coprime moduli: a solution exists only if the residues agree modulo the gcd, and the new modulus is the lcm, not the product. A stress test checks 1000 random systems, 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

Dadi's laddoos. A tray of fewer than 100 laddoos. In boxes of 3, two are left over. In boxes of 5, three are left over. In boxes of 7, two are left over. There were 23 laddoos.

The clock and the calendar. A clock wraps around every 12 hours: 14:00 is 2 o'clock, because 14 mod 12 = 2. The week wraps every 7 days: 10 days after a Monday is a Thursday, because 10 mod 7 = 3.

Two trains. An express stops at a station every 4 days, first on day 2 (days 2, 6, 10, 14 …). A mail train stops every 6 days, first on day 4 (days 4, 10, 16, 22 …). Both stop on days 10, 22, 34: every 12 days (the lcm), not every 24. Move the express to days 1, 5, 9 (always odd) and the mail train to days 2, 8, 14 (always even), and they never meet.

Words first: remainder, mod, congruence

  • Remainder (also residue): what is left over after dividing. 23 laddoos in boxes of 5: 4 full boxes and 3 left over.
  • mod: the remainder operation. 23 mod 5 = 3; in C++, 23 % 5 == 3.
  • Congruence: a statement "x leaves r when divided by m", written x ≡ r (mod m) and read "x is congruent to r mod m". In code: x % m == r. Example: x ≡ 3 (mod 5).
  • Modulus: the m in a congruence (here 5).
  • One congruence has many answers, one every m: 3, 8, 13, 18, 23 … are all ≡ 3 (mod 5). A congruence is a repeating pattern.
  • Two numbers are congruent mod m when they differ by a multiple of m: 23 ≡ −82 (mod 105) because 23 − (−82) = 105.

Solving Dadi's puzzle by hand

  1. Numbers that leave 2 in threes: start at 2 and jump by 3: 2, 5, 8, 11, 14, 17, 20, 23 …
  2. Keep the ones that leave 3 in fives: 8, then 23 (15 apart, since 15 is the first multiple of both 3 and 5). The first two rules have merged into one: x ≡ 8 (mod 15).
  3. Start at 8 and jump by 15: 8, 23, 38 … 8 leaves 1 in sevens, 23 leaves 2. Done: x ≡ 23 (mod 105). The next answer, 128, is over 100.

The key idea: keep one merged rule x ≡ r (mod m) and fold the rules in one at a time.

Problem M · Laddoo Boxes

Problem M · Laddoo Boxes (written for this course). You are given k rules. Rule i says x % mi = ri. Print the smallest x ≥ 0 that follows every rule, or -1 if there is none.

Input: k, then k lines ri mi. 1 ≤ k ≤ 10^5, 1 ≤ mi ≤ 10^18, 0 ≤ ri < mi. It is guaranteed that the lcm of all mi is at most 10^18. Time limit 1 second.

Sample input Sample output Why
3 / 2 3 / 3 5 / 2 7 23 Dadi's laddoos
2 / 2 4 / 4 6 10 the trains meet on day 10, 22, 34 …
2 / 1 4 / 2 6 -1 always odd vs always even
2 / 3 5 / 0 1 3 a modulus-1 rule changes nothing

Brute force: try every x (Time Limit Exceeded)

Every rule repeats after its modulus, so the whole system repeats after the lcm L (episode 24). If nothing below L works, nothing ever will.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    vector<ll> r(k), m(k);
    for (int i = 0; i < k; i++) cin >> r[i] >> m[i];
    ll L = 1;                          // lcm, episode 24
    for (ll x : m) L = L / gcd(L, x) * x;
    for (ll x = 0; x < L; x++) {
        bool ok = true;
        for (int i = 0; i < k; i++)
            if (x % m[i] != r[i]) { ok = false; break; }
        if (ok) { cout << x << "\n"; return 0; }
    }
    cout << -1 << "\n";
    return 0;
}
Input Output
3 / 2 3 / 3 5 / 2 7 23
2 / 2 4 / 4 6 10
2 / 1 4 / 2 6 -1
4 / 2 3 / 3 5 / 2 7 / 4444444444444444 9000000000000001 Time Limit Exceeded

Why: the answer to the big test is 40444444444444448 ≈ 4·10^16. At 10^9 checks a second, counting up to it takes over a year.

Smarter: jump by m (still Time Limit Exceeded)

The hand method in code: keep x ≡ r (mod m), and for each new rule jump r forward by m until it fits. If mi jumps don't help, nothing will (the pattern repeats), so print -1. Then the step becomes lcm(m, mi).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    ll r = 0, m = 1;                   // x = r, step m
    while (k--) {
        ll ri, mi;
        cin >> ri >> mi;
        ll steps = 0;
        while (r % mi != ri && steps < mi) r += m, steps++;
        if (steps == mi) { cout << -1 << "\n"; return 0; }
        m = m / gcd(m, mi) * mi;           // lcm
    }
    cout << r << "\n";
    return 0;
}

Real outputs: 23, 10, -1 on the three samples, and Time Limit Exceeded on the big test: after the three small rules the step is 105, and the last rule needs (40444444444444448 − 23) / 105 ≈ 3.85·10^14 jumps. We are guessing the number of jumps one at a time. We should solve for it.

The key observation: merging two rules is episode 25's equation

Every x with x ≡ r (mod m) is x = r + m·t for some whole number t (the number of jumps). The new rule needs:

r + m·t ≡ ri (mod mi)
m·t ≡ ri − r (mod mi)
m·t + mi·s = ri − r          for some whole s   ← linear Diophantine equation (episode 25)

ext_gcd(m, mi) gives p, q and g = gcd(m, mi) with m·p + mi·q = g.

  • Solvable only if g divides ri − r (episode 25's rule). Otherwise print -1.
  • Multiply by (ri − r) / g: t = p · (ri − r) / g, and every t that works repeats every mi / g, so reduce t mod (mi / g).
  • Normalise: p can be negative, so t can be negative; if t < 0, add mi / g.
  • New rule: r ← r + m·t, m ← lcm(m, mi) = m / g · mi.

Start with r = 0, m = 1 (x ≡ 0 (mod 1): every number fits) and merge the rules one by one. If all moduli are pairwise coprime (gcd 1, no common factor, like 15 and 7), g is always 1 and the answer exists for any residues: that is the classical Chinese remainder theorem. The general version above handles any moduli.

First attempt: the coprime-only formula

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

ll ext_gcd(ll a, ll b, ll &x, ll &y) {   // episode 25
    if (b == 0) { x = 1, y = 0; return a; }
    ll g = ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    ll r = 0, m = 1;                   // x ≡ 0 (mod 1)
    while (k--) {
        ll ri, mi;
        cin >> ri >> mi;
        ll p, q, g = ext_gcd(m, mi, p, q);
        ll md = mi;                    // assume g = 1
        ll t = (__int128)p * (ri - r) % md;
        if (t < 0) t += md;            // normalise
        r += m * t;                    // stays below the lcm
        m = m * mi;
    }
    cout << r << "\n";
    return 0;
}
Input Real output Expected
3 / 2 3 / 3 5 / 2 7 23 23
2 / 2 4 / 4 6 18 10 (18 % 6 = 0, not 4)
2 / 1 4 / 2 6 21 -1 (21 % 6 = 3, not 2)

The laddoo moduli are coprime, so they hide the bug; 4 and 6 share the factor 2.

The trains: the gcd check and the lcm

  • The express (x ≡ 2 (mod 4)) and the mail train (x ≡ 4 (mod 6)) are both always on even days, so they agree mod gcd(4, 6) = 2 and they meet: days 10, 22, 34 … every lcm(4, 6) = 12 days.
  • x ≡ 1 (mod 4) is always odd and x ≡ 2 (mod 6) always even: they disagree mod 2, so there is no solution. In formula terms, g = 2 does not divide 2 − 1 = 1.

Rule: x ≡ r1 (mod m1) and x ≡ r2 (mod m2) have a common solution if and only if r1 ≡ r2 (mod gcd(m1, m2)), and then the solutions repeat every lcm(m1, m2).

Trace: merging Dadi's three rules

The ext_gcd above returns these exact p values.

Step Rule ext_gcd ri − r t new r new m
start 0 1
1 2 mod 3 1·1 + 3·0 = 1, p = 1 2 2 0 + 1·2 = 2 3
2 3 mod 5 3·2 + 5·(−1) = 1, p = 2 1 2 2 + 3·2 = 8 15
3 2 mod 7 15·1 + 7·(−2) = 1, p = 1 −6 −6 → +7 → 1 8 + 15·1 = 23 105

Step 3 shows why normalising matters: without it, r = 8 + 15·(−6) = −82.

The accepted solution

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

ll ext_gcd(ll a, ll b, ll &x, ll &y) {   // episode 25
    if (b == 0) { x = 1, y = 0; return a; }
    ll g = ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    ll r = 0, m = 1;                   // x ≡ 0 (mod 1)
    while (k--) {
        ll ri, mi;
        cin >> ri >> mi;
        ll p, q, g = ext_gcd(m, mi, p, q);
        if ((ri - r) % g != 0) { cout << -1 << "\n"; return 0; }
        ll md = mi / g;
        ll t = (__int128)p * ((ri - r) / g) % md;
        if (t < 0) t += md;            // normalise
        r += m * t;                    // stays below the lcm
        m = m / g * mi;                // lcm(m, mi)
    }
    cout << r << "\n";
    return 0;
}

Why __int128? |p| can be close to mi / g and |ri − r| close to max(m, mi), so their product can reach about 10^36, far beyond a long long (about 9.2·10^18). __int128 is g++'s 128-bit integer type, holding up to about 1.7·10^38. Only this one multiplication needs it: after it, t < mi / g, so r + m·t < m · mi / g = lcm ≤ 10^18 fits in a long long, and so does the new modulus (computed as m / g · mi, dividing first).

Input Output
3 / 2 3 / 3 5 / 2 7 23
2 / 2 4 / 4 6 10
2 / 1 4 / 2 6 -1
2 / 3 5 / 0 1 3
1 / 0 1 0
4 / 2 3 / 3 5 / 2 7 / 4444444444444444 9000000000000001 40444444444444448 (instant)
2 / 123456789 999999937 / 987654321 1000000007 359082872501234404
3 / 2 4 / 4 6 / 1 5 46

The two large answers were cross-checked with Python's exact big integers.

A stress test

Non-coprime moduli and missing solutions are easy to get wrong, so (episode 5) compare against a brute force on 1000 random small systems: up to 3 rules, moduli 1 … 12. Every lcm here is below 1000 (the biggest is lcm(9, 10, 11) = 990), so a brute force over x < 1000 is always right.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1, y = 0; return a; }
    ll g = ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
ll crt(vector<ll>& R, vector<ll>& M) {
    ll r = 0, m = 1;
    for (int i = 0; i < (int)R.size(); i++) {
        ll p, q, g = ext_gcd(m, M[i], p, q);
        if ((R[i] - r) % g != 0) return -1;
        ll md = M[i] / g, t = (__int128)p * ((R[i] - r) / g) % md;
        if (t < 0) t += md;
        r += m * t, m = m / g * M[i];
    }
    return r;
}
int main() {
    mt19937 rng(26);
    for (int t = 1; t <= 1000; t++) {
        int k = rng() % 3 + 1;
        vector<ll> R(k), M(k);
        for (ll &x : M) x = rng() % 12 + 1;
        for (int i = 0; i < k; i++) R[i] = rng() % M[i];
        ll b = -1;                     // brute: smallest x < 1000
        for (ll x = 999; x >= 0; x--) {
            bool ok = true;
            for (int i = 0; i < k; i++) ok &= x % M[i] == R[i];
            if (ok) b = x;
        }
        if (crt(R, M) != b) { cout << "mismatch " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}

Real output:

all 1000 tests passed

Complexity vs the constraints

Approach Time Worst case here Verdict
Try every x up to the lcm O(lcm · k) 10^18 TLE
Jump by m O(Σ mi / g) up to ~10^18 jumps TLE
Merge with ext_gcd O(k · log mi) 10^5 · ~90 ≈ 10^7 instant

Memory: O(1) beyond the input. The running time does not depend on the size of the answer. Extended Euclid takes O(log) steps like the gcd: fewer than 90 for numbers up to 10^18 (the worst case is consecutive Fibonacci numbers).

The rule: never search for a number you can solve for.

Common mistakes (and the real outputs)

Bug 1: no __int128

        ll t = p * ((ri - r) / g) % md;   // no int128

Big test 4 / 2 3 / 3 5 / 2 7 / 4444444444444444 9000000000000001 → 725303668930360193 (expected 40444444444444448). In the last merge p = 2485714285714286 and ri − r = 4444444444444421: their product (about 1.1·10^31) overflows long long and wraps to garbage. All the small samples still pass, so only a large test catches this.

Bug 2: not normalising t

Remove if (t < 0) t += md;. 3 / 2 3 / 3 5 / 2 7 → -82 (expected 23). In the last merge t = −6 (see the trace), so r = 8 + 15·(−6) = −82 = 23 − 105: the right pattern, but not the smallest answer ≥ 0.

Bug 3: the product instead of the lcm

        m = m * mi;                    // product

3 / 2 4 / 4 6 / 1 5 → 106 (expected 46). After the trains, the true rule is x ≡ 10 (mod 12). The product says mod 24, which keeps only 10, 34, 58, 82, 106 … and throws away 22 and 46. 46 also leaves 1 in fives. (With coprime moduli the product is the lcm, so the laddoo samples never show this.)

Summary table

Mistake What you see Why Fix
assume gcd = 1 18 instead of 10; 21 instead of -1 4 and 6 share the factor 2 check (ri - r) % g, divide by g, reduce mod mi / g
ll t = p * ((ri - r) / g) % md; 725303668930360193 p · (ri − r) / g overflows (__int128)p * …
no if (t < 0) t += md; -82 instead of 23 ext_gcd gives a negative p normalise t
m = m * mi; 106 instead of 46 the trains meet every 12, not 24 m = m / g * mi
for (ll x = 0; x < L; x++) Time Limit Exceeded answer up to 10^18 merge with ext_gcd

Mini project

Write a reusable pair<ll, ll> crtMerge(ll r1, ll m1, ll r2, ll m2) that returns the merged (r, m), or (−1, −1) when the rules conflict, plus a stress tester against brute force for all moduli ≤ 12. Then build on it: (1) the smallest x ≥ L that fits all rules; (2) how many x in [1, N] fit; (3) a "festival calendar": given k festivals that repeat every mi days starting on day ri, print the first day all of them fall together, or "never".

Practice

These follow the video's homework.

  1. Smallest x ≥ L that follows every rule. Example: Dadi's three rules, L = 100.

    Answer Merge everything into x ≡ r (mod m) (here 23 mod 105). If r ≥ L the answer is r; otherwise jump in one step: r + ⌈(L − r) / m⌉ · m. Here 23 + 1 · 105 = <b>128</b> (checked by brute force).

  2. How many x in [1, N] follow every rule? Example: Dadi's rules, N = 1000.

    Answer The solutions are r, r + m, r + 2m … Count those ≤ N (and ≥ 1; if r = 0, start at m): ⌊(N − r) / m⌋ + 1 when r ≥ 1 and r ≤ N. Here ⌊(1000 − 23) / 105⌋ + 1 = 9 + 1 = <b>10</b> (checked by brute force).

  3. Dadi's puzzle with a fourth rule: 1 mod 9.

    Answer <b>-1</b>. 9 and 3 share the factor 3: 1 mod 9 forces x ≡ 1 (mod 3), but the first rule says x ≡ 2 (mod 3). gcd(105, 9) = 3 does not divide 1 − 23 = −22. (With 5 mod 9 instead, the answer is 23, because 23 % 9 = 5.) Checked by brute force.

  4. Three alarms ring every 4, 6 and 10 minutes, first at minutes 1, 3 and 5. When do all three ring together?

    Answer x ≡ 1 (mod 4), x ≡ 3 (mod 6), x ≡ 5 (mod 10). All residues are odd, so they agree mod 2; mod 3 x ≡ 0 and mod 5 x ≡ 0, so x is an odd multiple of 15 with x % 4 = 1: <b>45</b>, then every lcm = 60 minutes (checked by brute force).

  5. Without code: the smallest positive x that leaves 1, 2, 3, 4, 5 when divided by 2, 3, 4, 5, 6.

    Answer Every remainder is one less than the divisor, so x + 1 is divisible by 2, 3, 4, 5 and 6: x + 1 = lcm = 60, x = <b>59</b> (checked by brute force).

Quick quiz

The smallest x ≥ 0 with x % 4 = 1 and x % 6 = 3?

A) -1 (no answer) · B) 9 · C) 21 · D) 3

Answer

B. gcd(4, 6) = 2 divides 3 − 1 = 2 (both residues are odd), so a solution exists and repeats every lcm = 12: 9, 21, 33 … (checked by brute force). A is the "moduli must be coprime" trap. C is a solution but not the smallest. D fails: 3 % 4 = 3.

Interview questions

  1. State the Chinese remainder theorem. If m1 … mk are pairwise coprime, the system x ≡ ri (mod mi) has exactly one solution modulo m1 · m2 · … · mk, for any residues.
  2. What if the moduli are not coprime? Two rules x ≡ r1 (mod m1), x ≡ r2 (mod m2) are solvable iff r1 ≡ r2 (mod gcd(m1, m2)); the solution is unique modulo lcm(m1, m2).
  3. How do you merge two congruences? Write x = r1 + m1·t, solve m1·t ≡ r2 − r1 (mod m2) with extended Euclid: t = p · (r2 − r1) / g mod (m2 / g), then x ≡ r1 + m1·t (mod lcm).
  4. Where can it overflow, and how do you avoid it? In p · (r2 − r1) / g: use __int128 (or a mulmod). Compute the lcm as m1 / g · m2 (divide first).
  5. Why normalise? Extended Euclid's coefficients can be negative, so t (and the answer) can come out negative; add the modulus once.
  6. What is the complexity? O(k · log max mi): one extended Euclid per rule.
  7. Where is CRT used? Combining answers computed modulo several primes (e.g. nCr mod a square-free number), solving periodic-schedule problems, and in RSA decryption speed-ups.

Glossary

Term Meaning Example
Remainder / residue What is left over after dividing 23 in boxes of 5: 3 left
mod (%) The remainder operation 14 mod 12 = 2
Modulus The number you divide by in a congruence 5 in x ≡ 3 (mod 5)
Congruence x leaves r when divided by m: x ≡ r (mod m) 23 ≡ 2 (mod 7)
Congruent mod m Differing by a multiple of m 23 ≡ −82 (mod 105)
System of congruences Several congruences that must all hold Dadi's three rules
gcd Greatest common divisor (episode 19) gcd(4, 6) = 2
Coprime gcd = 1: no common factor except 1 15 and 7
lcm Least common multiple: smallest number both divide (episode 24) lcm(4, 6) = 12
Extended Euclid (ext_gcd) Finds p, q with a·p + b·q = gcd(a, b) (episode 25) 15·1 + 7·(−2) = 1
Linear Diophantine equation a·x + b·y = c in whole numbers (episode 25) m·t + mi·s = ri − r
Merging Replacing two congruences by one equivalent congruence 2 mod 3 and 3 mod 5 → 8 mod 15
Normalising Bringing a value back into 0 … modulus − 1 t = −6 → 1 (mod 7)
Chinese remainder theorem (CRT) Coprime moduli: exactly one solution modulo their product 23 mod 105
__int128 g++'s 128-bit integer type, up to about 1.7·10^38 holds 10^18 · 10^18
Integer overflow A value too big for its type wraps around 725303668930360193
Stress test Comparing a fast solution with a brute force on many random small tests all 1000 tests passed

Summary

  • x ≡ r (mod m) means x % m == r: a repeating pattern, one value every m.
  • Keep one merged rule x ≡ r (mod m), starting from 0 mod 1, and fold in the rules one by one.
  • Merging is episode 25's equation m·t + mi·s = ri − r: solvable only if g = gcd(m, mi) divides ri − r (otherwise -1); t = p · (ri − r) / g mod (mi / g), normalised to ≥ 0; r ← r + m·t; m ← lcm = m / g · mi.
  • Multiply p · (ri − r) / g in __int128; everything else fits in long long because the lcm ≤ 10^18.
  • Brute force and jumping: TLE on the big test. Merging: 40444444444444448 instantly, O(k · log).
  • Real bugs: the coprime-only formula (18, 21), no __int128 (725303668930360193), no normalising (-82), product instead of lcm (106).

Solutions in C++, Java and Python

Problem M · Laddoo Boxes

C++: the accepted solution above.

Java (tested on all four samples, 1 / 0 1 → 0, the big test → 40444444444444448, the two-primes test → 359082872501234404, 3 / 2 4 / 4 6 / 1 5 → 46, and 150 random small systems against brute force). Java has no 128-bit integer, so the one big multiplication uses BigInteger; its mod() is never negative, which also normalises t.

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static long px, py;                       // ext_gcd's x and y

    static long extGcd(long a, long b) {
        if (b == 0) { px = 1; py = 0; return a; }
        long g = extGcd(b, a % b);
        long t = px; px = py; py = t - (a / b) * py;
        return g;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());
        long r = 0, m = 1;
        for (int i = 0; i < k; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long ri = Long.parseLong(st.nextToken()), mi = Long.parseLong(st.nextToken());
            long g = extGcd(m, mi), p = px;
            if ((ri - r) % g != 0) { System.out.println(-1); return; }
            long md = mi / g;
            // p * (ri - r) / g can pass 10^18: multiply as BigInteger, then reduce
            long t = BigInteger.valueOf(p).multiply(BigInteger.valueOf((ri - r) / g))
                     .mod(BigInteger.valueOf(md)).longValue();   // mod() is never negative
            r += m * t;
            m = m / g * mi;
        }
        System.out.println(r);
    }
}

Python (same tests, all match). Python integers never overflow and % with a positive modulus is never negative, so neither __int128 nor the normalising line is needed.

import sys

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y

def main():
    data = sys.stdin.read().split()
    k = int(data[0])
    r, m = 0, 1
    for i in range(k):
        ri, mi = int(data[1 + 2 * i]), int(data[2 + 2 * i])
        g, p, _ = ext_gcd(m, mi)
        if (ri - r) % g != 0:
            print(-1)
            return
        md = mi // g
        t = p * ((ri - r) // g) % md      # Python's % is never negative
        r += m * t
        m = m // g * mi
    print(r)

main()