Problem 531: Chinese Leftovers

Mathematical Foundation

The Extended Chinese Remainder Theorem

Theorem 1 (Extended CRT). Let $n, m \ge 1$ be positive integers and let $a, b \in \mathbb{Z}$. The system

has a solution if and only if $\gcd(n, m) \mid (a - b)$. When a solution exists, it is unique modulo $\operatorname{lcm}(n, m)$.

Proof. Set $d = \gcd(n, m)$.

Necessity. Suppose $x_0$ satisfies both congruences. Then $n \mid (x_0 - a)$ and $m \mid (x_0 - b)$. Since $d \mid n$ and $d \mid m$, we have $d \mid (x_0 - a)$ and $d \mid (x_0 - b)$, whence $d \mid \bigl((x_0 - a) - (x_0 - b)\bigr) = b - a$. Thus $d \mid (a - b)$.

Sufficiency. Assume $d \mid (a - b)$. By Bezout’s identity, there exist $u, v \in \mathbb{Z}$ with $un + vm = d$. Define

The fraction $(b - a)/d$ is an integer by hypothesis. Clearly $n \mid (x_0 - a)$, so $x_0 \equiv a \pmod{n}$. For the second congruence, observe

Since $un + vm = d$, we have $1 - nu/d = vm/d$, giving

Now $d \mid (a - b)$ by hypothesis, so $(a - b)/d \in \mathbb{Z}$, and thus $m \mid (x_0 - b)$.

Uniqueness. If $x_0$ and $x_1$ both satisfy the system, then $n \mid (x_1 - x_0)$ and $m \mid (x_1 - x_0)$. By the characterization of the least common multiple, $\operatorname{lcm}(n, m) \mid (x_1 - x_0)$. Hence $x_0 \equiv x_1 \pmod{\operatorname{lcm}(n, m)}$. $\blacksquare$

Corollary 1. The smallest non-negative solution is $x_0 \bmod \operatorname{lcm}(n, m)$, where $x_0$ is the value constructed in the sufficiency proof.

Euler’s Totient Sieve

Lemma 1 (Totient Sieve). Euler’s totient function $\varphi(k)$ for all $k \le N$ can be computed in $O(N \log \log N)$ time and $O(N)$ space.

Proof. Initialize an array $\varphi[k] = k$ for $0 \le k \le N$. For each prime $p \le N$ (identified when $\varphi[p] = p$), iterate over all multiples $k$ of $p$ and set $\varphi[k] \leftarrow \varphi[k] \cdot (1 - 1/p) = \varphi[k] - \varphi[k]/p$. By the Euler product formula,

each factor $(1 - 1/p)$ is applied exactly once for each prime $p \mid k$, so the final value of $\varphi[k]$ equals $\varphi(k)$. The total number of updates is $\sum_{p \le N} \lfloor N/p \rfloor = O(N \log \log N)$ by Mertens’ theorem. $\blacksquare$

Editorial

Compute S = sum of g(phi(n), n, phi(m), m) over 1000000 <= n < m <= 1005000, where g(a,n,b,m) is the smallest non-negative solution to the system x = a (mod n), x = b (mod m), or 0 if none exists. Method: Extended CRT via Bezout’s identity; totient sieve for phi values.

Pseudocode

    N_MAX = 1005000
    phi = TOTIENT_SIEVE(N_MAX)

    S = 0
    For n from 1000000 to 1005000:
        For m from n+1 to 1005000:
            a = phi[n], b = phi[m]
            d = gcd(n, m)
            If (a - b) mod d != 0 then
                continue
            (g, u, v) = EXTENDED_GCD(n, m)
            L = n / d * m
            x = (a + n * ((b - a) / d) * u) mod L
            if x < 0: x += L
            S += x
    Return S

Complexity Analysis

• Totient sieve: $O(N \log \log N)$ time, $O(N)$ space, with $N = 1\,005\,000$.
• Double loop: $\binom{5001}{2} \approx 1.25 \times 10^7$ pairs, each requiring $O(\log N)$ for the extended Euclidean algorithm. Total: $O(K^2 \log N)$ where $K = 5001$.
• Overall: $O(N \log \log N + K^2 \log N)$ time, $O(N)$ space.

Answer

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

typedef long long ll;
typedef __int128 lll;

/*
 * Problem 531: Chinese Leftovers
 *
 * Compute S = sum of g(phi(n), n, phi(m), m) over 1000000 <= n < m <= 1005000.
 * g(a,n,b,m) = smallest non-negative x with x=a(mod n), x=b(mod m), or 0.
 *
 * Method: Euler totient sieve + extended CRT via Bezout's identity.
 * Time: O(N log log N + K^2 log N).
 */

ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if (a == 0) { x = 0; y = 1; return b; }
    ll x1, y1;
    ll g = extended_gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return g;
}

ll crt(ll a, ll n, ll b, ll m) {
    ll u, v;
    ll g = extended_gcd(n, m, u, v);
    if ((a - b) % g != 0) return 0;
    ll mg = m / g;
    ll diff = ((lll)(b - a) / g % mg * u % mg + mg) % mg;
    ll lcm = n / g * m;
    ll x = (lll)a + (lll)n * diff;
    x = ((x % lcm) + lcm) % lcm;
    return x;
}

int main() {
    const int LO = 1000000, HI = 1005000;
    vector<ll> phi(HI + 1);
    iota(phi.begin(), phi.end(), 0);
    for (int i = 2; i <= HI; i++) {
        if (phi[i] == i) {
            for (int j = i; j <= HI; j += i)
                phi[j] -= phi[j] / i;
        }
    }

    ll S = 0;
    for (int n = LO; n <= HI; n++)
        for (int m = n + 1; m <= HI; m++)
            S += crt(phi[n], n, phi[m], m);

    cout << S << endl;
    return 0;
}

"""
Problem 531: Chinese Leftovers

Compute S = sum of g(phi(n), n, phi(m), m) over 1000000 <= n < m <= 1005000,
where g(a,n,b,m) is the smallest non-negative solution to the system
x = a (mod n), x = b (mod m), or 0 if none exists.

Method: Extended CRT via Bezout's identity; totient sieve for phi values.
"""

from math import gcd

def extended_gcd(a, b):
    """Return (g, x, y) such that a*x + b*y = g = gcd(a, b)."""
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

def crt(a, n, b, m):
    """Smallest non-negative x with x = a (mod n), x = b (mod m), or 0."""
    d = gcd(n, m)
    if (a - b) % d != 0:
        return 0
    lcm = n // d * m
    _, u, _ = extended_gcd(n, m)
    x = (a + n * ((b - a) // d) * u) % lcm
    return x

def euler_totient_sieve(limit):
    """Compute phi(k) for k = 0..limit via the Euler product sieve."""
    phi = list(range(limit + 1))
    for i in range(2, limit + 1):
        if phi[i] == i:  # i is prime
            for j in range(i, limit + 1, i):
                phi[j] -= phi[j] // i
    return phi

LO, HI = 1000000, 1005000
phi = euler_totient_sieve(HI)

S = 0
for n in range(LO, HI + 1):
    for m in range(n + 1, HI + 1):
        S += crt(phi[n], n, phi[m], m)

print(S)