Chinese Remainder Theorem

Nguyên tố cùng nhau

Tìm $x$ với $x \equiv a \pmod n$ và $x \equiv b \pmod m$, $\gcd(n, m) = 1$. Mọi $x$ thỏa điều kiện đầu có dạng $x = a + n t$. Thay vào điều kiện sau:

Nghịch đảo $n^{-1} \bmod m$ tồn tại vì $\gcd(n, m) = 1$, lấy từ Euclid mở rộng $n p + m q = 1$. Với $t \in [0, m)$, nghiệm $x = a + n t$ nằm trong $[0, nm)$, và mọi nghiệm cách nhau đúng $nm$: hai nghiệm có hiệu chia hết cho cả $n$ lẫn $m$, nên chia hết cho $nm$.

Hình dưới ghép lần lượt: mỗi hàng là các số thỏa một đồng dư, hàng cuối là các số thử theo bước của mô-đun đã ghép.

Ví dụGhép Hai Số Dư

Đề. $T \le 1000$ bộ $a, n, b, m$ với $n, m \le 10^9$ nguyên tố cùng nhau. In $x$ không âm nhỏ nhất thỏa $x \bmod n = a$, $x \bmod m = b$, và $K = nm$.

Lời giải. Mọi $x$ thỏa điều kiện đầu có dạng $x = a + n t$. Thay vào điều kiện thứ hai: $n t \equiv b - a \pmod m$. Vì $\gcd(n, m) = 1$, $n$ có nghịch đảo $p$ theo mô-đun $m$, lấy từ Euclid mở rộng $n p + m q = 1$, nên $t \equiv (b - a) \cdot p \pmod m$. Lấy $t \in [0, m)$ thì $x = a + n t$ nằm trong $[0, nm)$ và là nghiệm không âm nhỏ nhất.

Bước 1: Euclid mở rộng. Lời gọi con trên $(b, a \bmod b)$ cho $b x' + (a \bmod b) y' = d$; thay $a \bmod b = a - \lfloor a/b \rfloor b$ được $x = y'$, $y = x' - \lfloor a/b \rfloor y'$. Truyền y, x theo thứ tự đảo vào lời gọi con rồi sửa y là đúng hai đẳng thức đó.

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

Bước 2: tính $t$ và $x$. Hệ số p có thể âm, đưa về $[0, m)$; $b - a$ cũng đưa về không âm trước khi nhân. Cả hai thừa số dưới $10^9$ nên tích dưới $10^{18}$; a + n * t không quá $(n - 1) + n(m - 1) < nm$.

exgcd(n, m, p, q);
p = (p % m + m) % m;
ll t = ((b - a) % m + m) % m * p % m;
cout << a + n * t << ' ' << n * m << '\n';

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

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll a, n, b, m, p, q;
        cin >> a >> n >> b >> m;
        exgcd(n, m, p, q);
        p = (p % m + m) % m;
        ll t = ((b - a) % m + m) % m * p % m;
        cout << a + n * t << ' ' << n * m << '\n';
    }
}

ChạyInput2
2 3 3 5
1 4 3 7

Output8 15
17 28

Độ phức tạp: mỗi bộ $O(\log m)$.

Có ước chung

Đặt $g = \gcd(n, m)$. Phương trình $a + n t \equiv b \pmod m$ có nghiệm khi và chỉ khi $g \mid (b - a)$: vế trái và $m$ cùng chia hết cho $g$ ở phần $n t$. Khi đó chia cả ba cho $g$:

Euclid mở rộng cho $n p + m q = g$, và $p$ chính là nghịch đảo của $n/g$ theo mô-đun $m/g$. Nghiệm $x = a + n t$ với $t \in [0, m/g)$, chu kỳ $K = \frac{n}{g} \cdot m = \operatorname{lcm}(n, m)$. Viết $n / g \cdot m$ thay vì $n \cdot m / g$ để khỏi tràn.

Ví dụHai Lịch Không Đồng Nguyên

Đề. Như bài trên nhưng $n, m \le 10^9$ có thể có ước chung. In no solution, hoặc $x \in [0, K)$ cùng $K = \operatorname{lcm}(n, m)$.

Lời giải. Như bài trên, cần $n t \equiv b - a \pmod m$, nhưng giờ $g = \gcd(n, m)$ có thể khác 1. Vế trái và mô-đun đều chia hết cho $g$, nên có nghiệm khi và chỉ khi $g \mid (b - a)$. Khi đó chia cả ba cho $g$: $\frac{n}{g} t \equiv \frac{b - a}{g} \pmod{\frac{m}{g}}$, với $\frac{n}{g}$ và $\frac{m}{g}$ nguyên tố cùng nhau. Hệ số $p$ của $n p + m q = g$ chính là nghịch đảo của $\frac{n}{g}$ theo mô-đun $\frac{m}{g}$. Chu kỳ là $\operatorname{lcm}(n, m) = \frac{n}{g} \cdot m$.

Bước 1: kiểm có nghiệm. g lấy luôn từ giá trị trả về của exgcd. Phép % với số âm cho kết quả âm hoặc 0, nhưng ở đây chỉ cần biết có bằng 0 hay không.

ll g = exgcd(n, m, p, q);
if ((b - a) % g) {
    cout << "no solution\n";
    continue;
}

Bước 2: giải theo mô-đun $m/g$. Chu kỳ in bằng n / g * m: chia trước rồi mới nhân để khỏi tràn.

ll mg = m / g;
p = (p % mg + mg) % mg;
ll t = ((b - a) / g % mg + mg) % mg * p % mg;
cout << a + n * t << ' ' << n / g * m << '\n';

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

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll a, n, b, m, p, q;
        cin >> a >> n >> b >> m;
        ll g = exgcd(n, m, p, q);
        if ((b - a) % g) {
            cout << "no solution\n";
            continue;
        }
        ll mg = m / g;
        p = (p % mg + mg) % mg;
        ll t = ((b - a) / g % mg + mg) % mg * p % mg;
        cout << a + n * t << ' ' << n / g * m << '\n';
    }
}

ChạyInput2
2 4 6 8
1 2 0 4

Output6 8
no solution

Độ phức tạp: mỗi bộ $O(\log m)$.

Ghép nhiều điều kiện

Giữ một đồng dư gộp $x \equiv R \pmod M$, bắt đầu từ $R = 0, M = 1$, rồi ghép từng điều kiện vào. Sau mỗi bước $M$ là $\operatorname{lcm}$ các mô-đun đã ghép và $0 \le R < M$. Gặp một bước vô nghiệm thì cả hệ vô nghiệm.

Chỗ dễ sai là tràn số: khi $M$ và $m_i$ lớn, tích $\frac{b - R}{g} \cdot p$ trước khi lấy dư có thể vượt $10^{18}$. Nhân bằng __int128 (hoặc nhân Ấn Độ) ở đúng bước này. Còn $R + M t < \operatorname{lcm}$ thì vừa long long nếu đề bảo đảm $\operatorname{lcm} \le 10^{18}$. Nhớ đưa $r_i$ về $[0, m_i)$ trước khi ghép, nhất là khi đề cho số âm hoặc lớn hơn mô-đun.

Hai cách nhân modulo cho số lớn khác nhau rất xa về tốc độ:

__int128 nhanh hơn nhân Ấn Độ (nhân bằng cộng gấp đôi) khoảng 9 lần, vì chỉ là một phép nhân và một phép chia phần cứng. Quy tắc: ưu tiên __int128; nhân Ấn Độ chỉ khi trình biên dịch không có.

Ví dụHợp Nhất Nhiều Chu Kỳ

Đề. $n \le 10^5$ đồng dư $x \equiv b_i \pmod{a_i}$, $a_i, b_i \le 10^{12}$, bội chung nhỏ nhất các $a_i$ không quá $10^{18}$, hệ luôn có nghiệm. In nghiệm không âm nhỏ nhất.

Lời giải. Giữ đồng dư gộp $x \equiv R \pmod M$, bắt đầu từ $R = 0$, $M = 1$ (mọi số nguyên đều thỏa). Ghép lần lượt từng điều kiện bằng đúng bước của bài trên, với $(R, M)$ đóng vai $(a, n)$. Sau mỗi bước $M$ là bội chung nhỏ nhất các mô-đun đã ghép và $0 \le R < M$. Đề bảo đảm có nghiệm nên không kiểm g | (b - R).

Bước 1: một bước ghép. b %= a đưa số dư về $[0, a)$. p là nghịch đảo của $M/g$ theo mô-đun $a/g$. Tích d * p giữa hai số tới $10^{12}$ thì vượt long long, nên chỉ bước đó nhân bằng __int128; kết quả lấy dư cho mg dưới $10^{12}$, ép về long long được.

b %= a;
ll g = exgcd(M, a, p, q), mg = a / g;
p = (p % mg + mg) % mg;
ll d = ((b - R) / g % mg + mg) % mg;
ll t = (ll)((__int128)d * p % mg);

Bước 2: cập nhật. $t < a/g$ nên $R + M t < M \cdot a / g$, chính là bội chung mới, không quá $10^{18}$. Chia trước, nhân sau.

R += M * t;
M = M / g * a;

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

ll n, R, M;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    R = 0, M = 1;
    for (ll i = 1; i <= n; i++) {
        ll a, b, p, q;
        cin >> a >> b;
        b %= a;
        ll g = exgcd(M, a, p, q), mg = a / g;
        p = (p % mg + mg) % mg;
        ll d = ((b - R) / g % mg + mg) % mg;
        ll t = (ll)((__int128)d * p % mg);
        R += M * t;
        M = M / g * a;
    }
    cout << R << '\n';
}

ChạyInput3
6 4
8 4
9 7

Output52

Độ phức tạp: $O(n \log a)$.

Đếm trong đoạn

Ghép xong còn $x \equiv R \pmod M$. Nghiệm đầu tiên không nhỏ hơn $lo$ là $f = lo + ((R - lo) \bmod M)$, phép dư lấy về không âm. Số nghiệm trong $[lo, hi]$ là $\lfloor (hi - f)/M \rfloor + 1$ nếu $f \le hi$, ngược lại 0.

Đề đòi số dương thì $lo = 1$. Cấp số cộng $a t + b$ với $t \ge 0$ thì $lo$ phải ít nhất là $b$.

Nhiều bài “hai chu kỳ trùng nhau” là CRT trá hình: lịch hai vòng, đèn nhấp nháy, tia sáng phản xạ khi trải gương ra. Khi trạng thái là một đoạn thời gian chứ không phải một thời điểm, duyệt các cặp độ lệch nhỏ và giải một CRT cho mỗi cặp.

Ví dụĐếm Nghiệm Trong Giới Hạn

Đề. $T \le 100$ test. Đếm số nguyên dương $X \le N \le 10^9$ thỏa $X \bmod a_i = b_i$ với $M \le 10$ điều kiện, $a_i \le 10$.

Lời giải. Ghép các đồng dư thành $X \equiv R \pmod M$ như bài trên; gặp bước vô nghiệm thì đáp án là 0. Nghiệm dương nhỏ nhất là $R$, hoặc $M$ nếu $R = 0$. Các nghiệm cách nhau $M$, nên số nghiệm không quá $N$ là $\lfloor (N - \text{first}) / M \rfloor + 1$ khi $\text{first} \le N$.

Bước 1: hàm ghép. Một bước ghép, trả về 0 khi vô nghiệm. Mô-đun tới 10 nên mọi tích đều nhỏ.

bool merge(ll r, ll m) {
    ll p, q, g = exgcd(M, m, p, q);
    if ((r - R) % g) return 0;
    ll mg = m / g;
    p = (p % mg + mg) % mg;
    ll t = ((r - R) / g % mg + mg) % mg * p % mg;
    R += M * t;
    M = M / g * m;
    return 1;
}

Bước 2: ghép và đếm. Đọc hết a[] rồi mới đọc b[], đúng thứ tự input. Vòng ghép dừng ngay khi một bước vô nghiệm.

R = 0, M = 1;
bool ok = 1;
for (ll i = 1; i <= k && ok; i++) ok = merge(b[i], a[i]);
ll first = R ? R : M;
if (!ok || first > N) cout << 0 << '\n';
else cout << (N - first) / M + 1 << '\n';

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

ll R, M, a[15], b[15];

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

bool merge(ll r, ll m) {
    ll p, q, g = exgcd(M, m, p, q);
    if ((r - R) % g) return 0;
    ll mg = m / g;
    p = (p % mg + mg) % mg;
    ll t = ((r - R) / g % mg + mg) % mg * p % mg;
    R += M * t;
    M = M / g * m;
    return 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll N, k;
        cin >> N >> k;
        for (ll i = 1; i <= k; i++) cin >> a[i];
        for (ll i = 1; i <= k; i++) cin >> b[i];
        R = 0, M = 1;
        bool ok = 1;
        for (ll i = 1; i <= k && ok; i++) ok = merge(b[i], a[i]);
        ll first = R ? R : M;
        if (!ok || first > N) cout << 0 << '\n';
        else cout << (N - first) / M + 1 << '\n';
    }
}

ChạyInput2
20 2
4 6
2 4
30 2
2 3
0 0

Output1
5

Độ phức tạp: mỗi test $O(M)$ bước ghép.

Ví dụGiao Hai Cấp Số Cộng

Đề. Đếm số nguyên trong $[L, R]$ có dạng $a_1 t + b_1$ và cũng có dạng $a_2 u + b_2$ với $t, u \ge 0$. $a_i \le 2 \cdot 10^9$, các số còn lại trong $[-2 \cdot 10^9, 2 \cdot 10^9]$.

Lời giải. $x = a_1 t + b_1$ với $t \ge 0$ nghĩa là $x \equiv b_1 \pmod{a_1}$ và $x \ge b_1$; tương tự cho dãy thứ hai. Vậy cần đếm $x \in [\max(L, b_1, b_2), R]$ thỏa hai đồng dư. Ghép hai đồng dư thành $x \equiv R_0 \pmod M$ bằng hàm merge như bài trên, rồi đếm số phần tử của cấp số cộng đó trong đoạn.

Bước 1: ghép. $b_i$ có thể âm, đưa về $[0, a_i)$ trước. Trong merge, d * p nhân bằng __int128 vì cả hai tới $2 \cdot 10^9$.

if (!merge((b1 % a1 + a1) % a1, a1) || !merge((b2 % a2 + a2) % a2, a2)) {
    cout << 0 << '\n';
    return 0;
}

Bước 2: số đầu tiên trong đoạn. lo là cận dưới thật của $x$. Số nhỏ nhất $\ge lo$ đồng dư với $R$ là $lo + ((R - lo) \bmod M)$, phép dư lấy về không âm. Bội chung tới $4 \cdot 10^{18}$, vẫn dưới giới hạn long long, nhưng cộng trừ quanh nó dễ tràn nên tính bằng __int128.

ll lo = max(L, max(b1, b2));
__int128 first = lo + (((__int128)R - lo) % M + M) % M;
if (first > Rg) cout << 0 << '\n';
else cout << (ll)((Rg - first) / M + 1) << '\n';

Cận phải đặt tên Rg để khỏi trùng với R của đồng dư.

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

ll R, M;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

bool merge(ll r, ll m) {
    ll p, q, g = exgcd(M, m, p, q);
    if ((r - R) % g) return 0;
    ll mg = m / g;
    p = (p % mg + mg) % mg;
    ll d = ((r - R) / g % mg + mg) % mg;
    ll t = (ll)((__int128)d * p % mg);
    R += M * t;
    M = M / g * m;
    return 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll a1, b1, a2, b2, L, Rg;
    cin >> a1 >> b1 >> a2 >> b2 >> L >> Rg;
    R = 0, M = 1;
    if (!merge((b1 % a1 + a1) % a1, a1) || !merge((b2 % a2 + a2) % a2, a2)) {
        cout << 0 << '\n';
        return 0;
    }
    ll lo = max(L, max(b1, b2));
    __int128 first = lo + (((__int128)R - lo) % M + M) % M;
    if (first > Rg) cout << 0 << '\n';
    else cout << (ll)((Rg - first) / M + 1) << '\n';
}

ChạyInput3 1 4 2 -10 30

Output2

Độ phức tạp: $O(\log a)$.