Định lý số dư Trung Hoa

Mức độ: Nâng cao

Bài toán cổ Hàn Tín điểm binh: cho quân xếp hàng 3 thì thừa 2 người, xếp hàng 5 thì thừa 3 người, xếp hàng 7 thì thừa 2 người. Hỏi có ít nhất bao nhiêu quân?

Viết theo đồng dư, cần tìm x sao cho

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

Định lý số dư Trung Hoa nói rằng: nếu các modulo đôi một nguyên tố cùng nhau thì hệ luôn có nghiệm, và các nghiệm cách nhau đúng tích các modulo (ở đây 3 × 5 × 7 = 105). Đáp số là 23 (rồi 128, 233, …).

Các bạn cần nắm vững bài Đồng dư và bài Thuật toán Euclid mở rộng trước khi học bài này.

Cách 1. Thử dần

Chỉ cần thử các số thỏa mãn đồng dư có modulo lớn nhất: 2, 9, 16, 23, … (thỏa mãn x ≡ 2 (mod 7)), rồi kiểm tra hai đồng dư còn lại.

x	x % 3	x % 5
2	2	2
9	0	4
16	1	1
23	2	3

Cách này cần thử tới m₁ × m₂ × … chia cho modulo lớn nhất số, chỉ dùng được khi các modulo nhỏ.

Cách 2. Ghép từng cặp đồng dư

Ghép hai đồng dư đầu thành một đồng dư, rồi ghép tiếp với đồng dư thứ ba, cứ thế đến hết.

Ghép x ≡ r₁ (mod m₁) với x ≡ r₂ (mod m₂): từ đồng dư thứ nhất, x = r₁ + m₁ × t. Thay vào đồng dư thứ hai:

m₁ × t ≡ r₂ - r₁ (mod m₂)

Đây là phương trình đồng dư đã giải ở bài Euclid mở rộng. Đặt g = ƯCLN(m₁, m₂):

Nếu r₂ - r₁ không chia hết cho g: hệ vô nghiệm.
Ngược lại: t = (r₂ - r₁) / g × p % (m₂ / g), với p là hệ số Bézout của m₁ (m₁ × p + m₂ × q = g). Hai đồng dư gộp thành x ≡ r₁ + m₁ × t (mod BCNN(m₁, m₂)).

Cách này dùng được cả khi các modulo không nguyên tố cùng nhau. Chạy với bài Hàn Tín:

Ghép	g	t	Kết quả
x ≡ 2 (mod 3) với x ≡ 3 (mod 5)	1	2	x ≡ 2 + 3 × 2 = 8 (mod 15)
x ≡ 8 (mod 15) với x ≡ 2 (mod 7)	1	1	x ≡ 8 + 15 × 1 = 23 (mod 105)

Python
C++

def euclid_mo_rong(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = euclid_mo_rong(b, a % b)
    return g, y1, x1 - (a // b) * y1

def ghep(r1, m1, r2, m2):
    """Gộp x ≡ r1 (mod m1) và x ≡ r2 (mod m2) thành (r, m); None nếu vô nghiệm."""
    g, p, _ = euclid_mo_rong(m1, m2)
    if (r2 - r1) % g != 0:
        return None
    m2g = m2 // g
    t = (r2 - r1) // g * p % m2g
    m = m1 * m2g                       # BCNN(m1, m2)
    return (r1 + m1 * t) % m, m

r, m = 0, 1                            # x ≡ 0 (mod 1): mọi số
for mi, ri in [(3, 2), (5, 3), (7, 2)]:
    r, m = ghep(r, m, ri, mi)
print(r, m)                            # 23 105

#include <iostream>
using namespace std;

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

// Gộp x ≡ r1 (mod m1) và x ≡ r2 (mod m2) thành x ≡ r (mod m); false nếu vô nghiệm.
// Giả sử BCNN không vượt quá 10^18; dùng __int128 khi nhân để không tràn.
bool ghep(long long r1, long long m1, long long r2, long long m2, long long &r, long long &m) {
    long long p, q;
    long long g = euclidMoRong(m1, m2, p, q);
    if ((r2 - r1) % g != 0) return false;
    long long m2g = m2 / g;
    __int128 t = (__int128)((r2 - r1) / g % m2g) * (p % m2g) % m2g;
    if (t < 0) t += m2g;
    m = m1 * m2g;
    r = (long long)(((__int128)r1 + (__int128)m1 * t) % m);
    return true;
}

int main() {
    long long r = 0, m = 1;
    long long cacM[3] = {3, 5, 7}, cacR[3] = {2, 3, 2};
    for (int i = 0; i < 3; i++) ghep(r, m, cacR[i], cacM[i], r, m);
    cout << r << " " << m << endl;     // 23 105
    return 0;
}

Lưu ý về tràn số: modulo sau khi gộp có thể tới 10¹⁸, và m₁ × t có thể vượt long long. Trong C++ phải nhân bằng __int128 như hàm trên. Python không bị tràn số.

Lưu ý về điểm bắt đầu: gộp bắt đầu từ x ≡ 0 (mod 1), tức “mọi số nguyên”. Như vậy không cần xử lý riêng đồng dư đầu tiên.

Khi các modulo không nguyên tố cùng nhau

x ≡ 5 (mod 12) và x ≡ 11 (mod 18): g = 6, và 11 - 5 = 6 chia hết cho 6, nên có nghiệm: x ≡ 29 (mod 36). Thử lại: 29 = 2 × 12 + 5 = 18 + 11.

x ≡ 1 (mod 4) và x ≡ 2 (mod 6): g = 2, 2 - 1 = 1 không chia hết cho 2, vô nghiệm. Dễ thấy vì đồng dư thứ nhất bắt x lẻ, đồng dư thứ hai bắt x chẵn.

Công thức khi các modulo nguyên tố cùng nhau

Khi các modulo đôi một nguyên tố cùng nhau, đặt M = m₁ × m₂ × … × m_k và M_i = M / m_i. Gọi y_i là nghịch đảo của M_i theo modulo m_i. Khi đó

x = (r₁ × M₁ × y₁ + … + r_k × M_k × y_k) % M

Mỗi số hạng r_i × M_i × y_i chia m_i dư r_i và chia hết cho mọi modulo khác. Với bài Hàn Tín: M = 105, ba số hạng là 2 × 35 × 2, 3 × 21 × 1, 2 × 15 × 1, tổng 233 ≡ 23 (mod 105).

Công thức đẹp nhưng chỉ dùng được khi các modulo nguyên tố cùng nhau. Khi lập trình, cách ghép từng cặp an toàn hơn.

Luyện tập

Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Hai đồng dư

Bài 1. Thử dần

Nhập bốn số r₁, m₁, r₂, m₂ (1 ≤ m₁, m₂ ≤ 1000, 0 ≤ r₁ nhỏ hơn m₁, 0 ≤ r₂ nhỏ hơn m₂). In ra số x ≥ 0 nhỏ nhất sao cho x chia m₁ dư r₁ và chia m₂ dư r₂, hoặc -1 nếu không có.

Ví dụ: nhập 2 3 3 5 thì in ra 8.

Kiểm tra: nhập 17 101 45 997.

Xem đáp số

40922

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Hai modulo nguyên tố cùng nhau

Nhập r₁, m₁, r₂, m₂ (1 ≤ m₁, m₂ ≤ 10⁹, ƯCLN(m₁, m₂) = 1, 0 ≤ r_i nhỏ hơn m_i). In ra số x ≥ 0 nhỏ nhất thỏa mãn x ≡ r₁ (mod m₁) và x ≡ r₂ (mod m₂).

Ví dụ: nhập 2 3 3 5 thì in ra 8.

Kiểm tra: nhập 123456 999999937 654321 1000000007.

Xem đáp số

214278118500601140

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Hai modulo bất kỳ

Nhập r₁, m₁, r₂, m₂ (1 ≤ m₁, m₂ ≤ 10⁹, 0 ≤ r_i nhỏ hơn m_i). In ra số x ≥ 0 nhỏ nhất thỏa mãn hai đồng dư, hoặc -1 nếu vô nghiệm. Các modulo không nhất thiết nguyên tố cùng nhau.

Ví dụ: nhập 5 12 11 18 thì in ra 29.

Kiểm tra: nhập 123456789 999999000 999789 1000000.

Xem đáp số

457122999789

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Đếm số thỏa mãn hai đồng dư

Nhập r₁, m₁, r₂, m₂, N (1 ≤ m_i ≤ 10⁹, 0 ≤ r_i nhỏ hơn m_i, 1 ≤ N ≤ 10¹⁸). Có bao nhiêu số x từ 1 đến N thỏa mãn x ≡ r₁ (mod m₁) và x ≡ r₂ (mod m₂)?

Ví dụ: nhập 2 3 3 5 100 thì in ra 7.

Kiểm tra: nhập 5 12 11 18 1000000.

Xem đáp số

27777

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Số thứ k

Nhập r₁, m₁, r₂, m₂, k (1 ≤ m_i ≤ 10⁶, 0 ≤ r_i nhỏ hơn m_i, 1 ≤ k ≤ 10⁶). In ra số nguyên dương thứ k (theo thứ tự tăng dần) thỏa mãn hai đồng dư, hoặc -1 nếu không có số nào.

Ví dụ: nhập 2 3 3 5 2 thì in ra 23.

Kiểm tra: nhập 5 12 11 18 1000.

Xem đáp số

35993

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Nhiều đồng dư

Bài 6. Hàn Tín điểm binh

Có ba dòng, mỗi dòng hai số m, r (1 ≤ m ≤ 100, 0 ≤ r nhỏ hơn m): xếp quân thành hàng m thì thừa r người. In ra số quân ít nhất có thể (một số ≥ 0), hoặc -1 nếu không thể xảy ra.

Ví dụ:

Nhập	In ra
`3 2` `5 3` `7 2`	`23`

Kiểm tra: nhập

7 3
11 5
13 9

Xem đáp số

269

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Nhiều modulo nguyên tố cùng nhau

Dòng đầu là n (1 ≤ n ≤ 20). n dòng sau, mỗi dòng hai số m_i, r_i (m_i ≥ 1, 0 ≤ r_i nhỏ hơn m_i), các m_i đôi một nguyên tố cùng nhau và tích của chúng không vượt quá 10¹⁸. In ra số x ≥ 0 nhỏ nhất thỏa mãn mọi đồng dư.

Ví dụ:

Nhập	In ra
`3` `3 2` `5 3` `7 2`	`23`

Kiểm tra: nhập

Xem đáp số

469650624774647498

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Nhiều modulo bất kỳ

Dòng đầu là n (1 ≤ n ≤ 10⁵). n dòng sau, mỗi dòng hai số m_i, r_i (1 ≤ m_i ≤ 10⁹, 0 ≤ r_i nhỏ hơn m_i). Biết BCNN của mọi m_i không vượt quá 10¹⁸. In ra số x ≥ 0 nhỏ nhất thỏa mãn mọi đồng dư, hoặc -1 nếu vô nghiệm.

Ví dụ:

Nhập	In ra
`3` `4 3` `6 5` `9 8`	`35`

Kiểm tra: nhập

Xem đáp số

579789

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Đếm trong một đoạn

Dòng đầu là n, L, R (1 ≤ n ≤ 10⁵, 1 ≤ L ≤ R ≤ 10¹⁸). n dòng sau, mỗi dòng hai số m_i, r_i như bài 8. Có bao nhiêu số x từ L đến R thỏa mãn mọi đồng dư?

Ví dụ:

Nhập	In ra
`2 1 100` `3 2` `5 3`	`7`

Kiểm tra: nhập

3 1 1000000000000
6 1
10 7
15 7

Xem đáp số

33333333334

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Hệ có hệ số

Dòng đầu là n (1 ≤ n ≤ 10). n dòng sau, mỗi dòng ba số a_i, b_i, m_i (0 ≤ a_i, b_i nhỏ hơn m_i, 1 ≤ m_i ≤ 10⁶), nghĩa là a_i × x ≡ b_i (mod m_i). Biết BCNN của mọi m_i không vượt quá 10¹⁸. In ra số x ≥ 0 nhỏ nhất thỏa mãn cả hệ, hoặc -1.

Ví dụ:

Nhập	In ra
`2` `2 1 3` `3 4 5`	`8`

Kiểm tra: nhập

Xem đáp số

139

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Bài toán thực tế

Bài 11. Ba ngọn đèn

Ba ngọn đèn nhấp nháy. Đèn thứ i lóe sáng lần đầu ở giây t_i, sau đó cứ p_i giây lại lóe sáng một lần. Có ba dòng, mỗi dòng hai số t_i, p_i (0 ≤ t_i ≤ 10⁶, 1 ≤ p_i ≤ 10⁶). In ra giây đầu tiên cả ba đèn cùng lóe sáng, hoặc -1 nếu không bao giờ.

Ví dụ:

Nhập	In ra
`2 3` `3 5` `2 7`	`23`

Kiểm tra: nhập

100 12
4 18
40 45

Xem đáp số

220

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Năm can chi

Năm âm lịch được gọi bằng một can (Giáp, Ất, Bính, Đinh, Mậu, Kỷ, Canh, Tân, Nhâm, Quý, lặp lại sau 10 năm) và một chi (Tý, Sửu, Dần, Mão, Thìn, Tỵ, Ngọ, Mùi, Thân, Dậu, Tuất, Hợi, lặp lại sau 12 năm). Năm 1984 là năm Giáp Tý, năm 1985 là Ất Sửu, và cứ thế. Nhập tên can, tên chi và một năm L (1 ≤ L ≤ 10⁹). In ra năm nhỏ nhất từ L trở đi có can chi đó, hoặc -1 nếu không có năm nào như vậy.

Ví dụ: nhập Bính Ngọ 2000 thì in ra 2026.

Kiểm tra: nhập Giáp Tý 2026.

Xem đáp số

2044

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Ba số liên tiếp

Nhập ba số nguyên dương a, b, c (a, b, c ≤ 10⁶). Tìm số nguyên dương x nhỏ nhất sao cho x chia hết cho a, x + 1 chia hết cho b và x + 2 chia hết cho c. In ra -1 nếu không có.

Ví dụ: nhập 2 3 5 thì in ra 8.

Kiểm tra: nhập 7 11 13.

Xem đáp số

791

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Thỏa mãn ít nhất một

Nhập r₁, m₁, r₂, m₂, N (1 ≤ m_i ≤ 10⁹, 0 ≤ r_i nhỏ hơn m_i, 1 ≤ N ≤ 10¹⁸). Có bao nhiêu số x từ 1 đến N thỏa mãn ít nhất một trong hai đồng dư x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂)?

Ví dụ: nhập 2 3 3 5 30 thì in ra 14.

Kiểm tra: nhập 5 12 11 18 1000000.

Xem đáp số

111111

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Hai dãy tuần hoàn

Dãy A gồm n số A₀, …, A_n-1 được viết lặp lại mãi: A₀, A₁, …, A_n-1, A₀, A₁, … Dãy B gồm m số cũng được viết lặp lại như vậy. Dòng đầu là n, m (1 ≤ n, m ≤ 300), hai dòng sau là các số của A và B (không quá 10⁹). Tìm vị trí i ≥ 0 nhỏ nhất mà phần tử thứ i của hai dãy bằng nhau (vị trí đầu tiên là 0). In ra -1 nếu không có.

Ví dụ:

Nhập	In ra
`3 4` `1 2 3` `4 5 6 3`	`11`

Kiểm tra: nhập

6 8
1 3 5 5 1 2
8 2 8 7 3 8 7 5

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Thừa và thiếu

Dòng đầu là n, L, R (1 ≤ n ≤ 10, 1 ≤ L ≤ R ≤ 10¹²). n dòng sau có dạng m thừa r (xếp hàng m thì thừa r người) hoặc m thiếu r (xếp hàng m thì hàng cuối thiếu r người), với 2 ≤ m ≤ 1000, 0 ≤ r nhỏ hơn m. In ra số quân nhỏ nhất trong đoạn từ L đến R, hoặc -1 nếu không có.

Ví dụ:

Nhập	In ra
`3 1000 1100` `3 thừa 2` `5 thừa 3` `7 thiếu 5`	`1073`

Kiểm tra: nhập

4 2000 5000
5 thiếu 1
6 thừa 5
7 thiếu 3
11 thừa 1

Xem đáp số

2069

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Số rất lớn

Bài 17. Nhân theo modulo lớn

Dòng đầu là n, m (1 ≤ n ≤ 10⁵, 2 ≤ m ≤ 10¹⁸). Dòng thứ hai có n số nguyên dương không quá 10¹⁸. In ra tích của n số chia lấy dư cho m.

Ví dụ:

Nhập	In ra
`3 1000000000000000000` `1000000000 1000000000 7`	`0`

Kiểm tra: nhập

6 999999999999999989
376625161664043530 808129322734854035 227670544625192561 618416730735372602 889956528077943303 883282125704228471

Xem đáp số

214709742004860396

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Lũy thừa theo modulo là tích hai số nguyên tố

Gọi P = 1000000007 × 998244353 (cả hai đều là số nguyên tố). Nhập n (0 ≤ n ≤ 10¹⁸). In ra 2ⁿ chia lấy dư cho P.

Ví dụ: nhập 10 thì in ra 1024.

Kiểm tra: nhập 1000000000000000000.

Xem đáp số

860803782745102692

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Nghiệm rất lớn: thuật toán Garner

Dòng đầu là n (1 ≤ n ≤ 1000). n dòng sau, mỗi dòng hai số m_i, r_i (2 ≤ m_i ≤ 2 × 10⁹, 0 ≤ r_i nhỏ hơn m_i), các m_i đôi một nguyên tố cùng nhau. Gọi x là số ≥ 0 nhỏ nhất thỏa mãn mọi đồng dư (x có thể có hàng nghìn chữ số). In ra x chia lấy dư cho 10⁹ + 7.

Ví dụ:

Nhập	In ra
`3` `3 2` `5 3` `7 2`	`23`

Kiểm tra: nhập

5
998244353 337405251
1000000009 225727008
999999937 426508939
754974721 270060143
167772161 93323692

Xem đáp số

782075277

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Hệ có nghiệm không

Dòng đầu là n (1 ≤ n ≤ 10⁵). n dòng sau, mỗi dòng hai số m_i, r_i (1 ≤ m_i ≤ 10⁶, 0 ≤ r_i nhỏ hơn m_i). Hệ đồng dư có nghiệm không? In ra CÓ hoặc KHÔNG. (BCNN của các m_i có thể rất lớn.)

Ví dụ:

Nhập	In ra
`3` `4 1` `6 3` `9 7`	`KHÔNG`

Kiểm tra: nhập

40
974461 251621
373962 132656
844248 837032
394627 82308
782208 55424
538537 302608
668697 382331
80029 13131
758239 249294
356931 9722
94022 24830
584531 126186
564203 464687
306313 205644
301574 56796
479670 420404
147734 106242
919052 86752
676118 390258
738173 386703
751217 622578
605474 494640
324010 186334
25943 7808
888978 303518
745395 467024
386763 175382
381203 228338
483471 217262
442729 321984
95091 68648
418146 194732
934250 682084
614171 25994
581383 557960
522670 450494
909353 158606
122106 260
446111 37053
530957 106384

Xem đáp số

CÓ

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English