Bài học

Số học modulo và các phép toán an toàn tràn số

Mục tiêu bài học

Sau bài này, em thực hiện đúng ba phép cộng, trừ, nhân theo modulo mà không sai dấu khi phép trừ ra số âm, và giải thích được vì sao gần như mọi bài đếm trong đề HSG QG yêu cầu in đáp số theo một modulo nguyên tố lớn thay vì in thẳng con số thật.

Cần nhớ trước

Em cần nhớ lại ba thứ: số nguyên tố và ước chung lớn nhất đã học ở khóa Tin học 10 HSG — Số học; phép chia lấy dư % trong Python; và ký hiệu đồng dư $a \equiv b \pmod{p}$ — nghĩa là $a$ và $b$ có cùng số dư khi chia cho $p$ .

Em cần nhớ lại ba thứ: số nguyên tố và ước chung lớn nhất đã học ở khóa Tin học 10 HSG — Số học; phép chia lấy dư `%` trong Python; và ký hiệu đồng dư $a \equiv b \pmod{p}$ — nghĩa là $a$ và $b$ có cùng số dư khi chia cho $p$.

So với mức chuẩn: chương trình Tin học 12 chuẩn dùng % như một công cụ kiểm tra chẵn lẻ hoặc lấy chữ số cuối của một số có sẵn — dừng lại ở đó. Số học modulo như một kỹ thuật kiểm soát độ lớn số không nằm trong yêu cầu cần đạt của Tin học 12 chuẩn; nó chỉ xuất hiện ở đề HSG QG và các kỳ thi lập trình. Toàn bộ khóa học này — từ bài hôm nay đến bài luyện tập tổng hợp cuối khóa — xây dựng đúng mảng kiến thức đó, trên nền số nguyên tố và ước chung lớn nhất em đã học ở khóa Tin học 10 HSG.

**So với mức chuẩn:** chương trình Tin học 12 chuẩn dùng `%` như một công cụ kiểm tra chẵn lẻ hoặc lấy chữ số cuối của một số có sẵn — dừng lại ở đó. Số học modulo như một kỹ thuật kiểm soát độ lớn số không nằm trong yêu cầu cần đạt của Tin học 12 chuẩn; nó chỉ xuất hiện ở đề HSG QG và các kỳ thi lập trình. Toàn bộ khóa học này — từ bài hôm nay đến bài luyện tập tổng hợp cuối khóa — xây dựng đúng mảng kiến thức đó, trên nền số nguyên tố và ước chung lớn nhất em đã học ở khóa Tin học 10 HSG.

Bài toán mở đầu — vì sao đáp số phải lấy dư

Một bài đếm điển hình trong đề HSG QG hỏi: có bao nhiêu cách sắp xếp, bao nhiêu tập con, bao nhiêu đường đi thỏa một điều kiện nào đó. Với $n$ đủ lớn, đáp số thật có thể lên tới hàng trăm chữ số — thử tính $2^{100}$ hay $50!$ sẽ thấy ngay. Trong Python, con số đó không hề tràn: kiểu int không có giới hạn độ dài, cộng hay nhân bao nhiêu chữ số cũng ra kết quả đúng tuyệt đối. Vậy vì sao đề vẫn bắt in đáp số theo modulo?

Một bài đếm điển hình trong đề HSG QG hỏi: có bao nhiêu cách sắp xếp, bao nhiêu tập con, bao nhiêu đường đi thỏa một điều kiện nào đó. Với $n$ đủ lớn, đáp số thật có thể lên tới hàng trăm chữ số — thử tính $2^{100}$ hay $50!$ sẽ thấy ngay. Trong Python, con số đó không hề tràn: kiểu `int` không có giới hạn độ dài, cộng hay nhân bao nhiêu chữ số cũng ra kết quả đúng tuyệt đối. Vậy vì sao đề vẫn bắt in đáp số theo modulo?

Lý do không nằm ở khả năng tính toán, mà ở khả năng chấm bài. Chương trình chấm tự động muốn kiểm tra đúng kỹ thuật số học modulo của em, không chỉ kiểm tra một con số hàng trăm chữ số. Ở C++ — ngôn ngữ thi đấu tham chiếu của các kỳ thi này — việc lấy dư còn bắt buộc hơn nữa: kiểu số nguyên có giới hạn cố định, một đáp số hàng trăm chữ số đơn giản là không lưu được. Python không có giới hạn đó, nên em dễ quên mất kỷ luật lấy dư từng bước — và đó chính là kỹ năng bài này rèn.

Ý tưởng cốt lõi — modulo tương thích với cộng, trừ, nhân

Viết $a = p \cdot q_a + r_a$ và $b = p \cdot q_b + r_b$ , với $r_a, r_b$ là phần dư khi chia $a, b$ cho $p$ . Khi đó $a+b = p(q_a+q_b) + (r_a+r_b)$ — phần dư của $a+b$ khi chia cho $p$ chỉ phụ thuộc $r_a+r_b$ , không phụ thuộc $q_a, q_b$ . Lập luận tương tự áp dụng cho phép trừ và phép nhân. Từ đó có một quy tắc dùng xuyên suốt khóa học này:

Viết $a = p \cdot q_a + r_a$ và $b = p \cdot q_b + r_b$, với $r_a, r_b$ là phần dư khi chia $a, b$ cho $p$. Khi đó $a+b = p(q_a+q_b) + (r_a+r_b)$ — phần dư của $a+b$ khi chia cho $p$ chỉ phụ thuộc $r_a+r_b$, không phụ thuộc $q_a, q_b$. Lập luận tương tự áp dụng cho phép trừ và phép nhân. Từ đó có một quy tắc dùng xuyên suốt khóa học này:

$(a \text{ op } b) \bmod p = \big((a \bmod p)\ \text{op}\ (b \bmod p)\big) \bmod p, \qquad \text{op} \in \{+, -, \times\}$

Hệ quả thực hành: cứ sau mỗi phép cộng, trừ, hoặc nhân, lấy % p ngay — kết quả trung gian không bao giờ vượt quá $p$ , và đáp số cuối cùng luôn đúng.

$$(a \text{ op } b) \bmod p = \big((a \bmod p)\ \text{op}\ (b \bmod p)\big) \bmod p, \qquad \text{op} \in \{+, -, \times\}$$ Hệ quả thực hành: cứ sau mỗi phép cộng, trừ, hoặc nhân, lấy `% p` ngay — kết quả trung gian không bao giờ vượt quá $p$, và đáp số cuối cùng luôn đúng.

Bốn bước áp dụng cho mọi phép cộng, trừ, nhân theo modulo trong suốt khóa học.

Ví dụ

Ví dụ 1 — Cộng, trừ, nhân modulo an toàn, kể cả khi phép trừ ra số âm

1
Bài chuẩn dùng % để kiểm tra chẵn lẻ hoặc lấy chữ số cuối của MỘT số có sẵn. Ở đây % phải áp dụng lặp lại qua một chuỗi phép toán, và một trong số đó — phép trừ — có thể cho kết quả âm nếu tính theo cách quen thuộc.
2
Cả ba phép đều theo đúng công thức ở trên, chỉ khác toán tử ở giữa:
```
def cong_mod(a, b, p):
    """Cong an toan theo modulo: luon dua ve [0, p) truoc khi tra ve."""
    return (a % p + b % p) % p
```
```
def tru_mod(a, b, p):
    """Tru an toan theo modulo. Python: % voi p duong LUON tra ve khong am,
    khac C++ (noi (a-b) % p co the am va phai tu cong them p)."""
    return (a % p - b % p) % p
```
```
def nhan_mod(a, b, p):
    """Nhan an toan theo modulo. Python int khong gioi han do dai nen a*b
    khong bao gio tran so du a, b lon co nao -- khac int32/int64 C++."""
    return (a % p) * (b % p) % p
```
Cả ba phép đều theo đúng công thức ở trên, chỉ khác toán tử ở giữa: ```python def cong_mod(a, b, p): """Cong an toan theo modulo: luon dua ve [0, p) truoc khi tra ve.""" return (a % p + b % p) % p ``` ```python def tru_mod(a, b, p): """Tru an toan theo modulo. Python: % voi p duong LUON tra ve khong am, khac C++ (noi (a-b) % p co the am va phai tu cong them p).""" return (a % p - b % p) % p ``` ```python def nhan_mod(a, b, p): """Nhan an toan theo modulo. Python int khong gioi han do dai nen a*b khong bao gio tran so du a, b lon co nao -- khac int32/int64 C++.""" return (a % p) * (b % p) % p ```
3
Toán tử % của Python được định nghĩa để luôn cho kết quả cùng dấu với $p$ — khi $p$ dương thì kết quả không âm, bất kể $a$ âm hay dương. C++ thì ngược lại: % lấy dấu theo số bị chia (chuẩn từ C++11), nên (a - b) % p có thể ra số âm và lập trình viên C++ phải tự sửa bằng ((a - b) % p + p) % p. Trong Python, tru_mod ở trên không cần bước sửa đó — đây là một trong số ít chỗ Python đơn giản hơn C++ thay vì ngược lại.
Toán tử `%` của Python được định nghĩa để luôn cho kết quả cùng dấu với $p$ — khi $p$ dương thì kết quả không âm, bất kể $a$ âm hay dương. C++ thì ngược lại: `%` lấy dấu theo số bị chia (chuẩn từ C++11), nên `(a - b) % p` có thể ra số âm và lập trình viên C++ phải tự sửa bằng `((a - b) % p + p) % p`. Trong Python, `tru_mod` ở trên không cần bước sửa đó — đây là một trong số ít chỗ Python đơn giản hơn C++ thay vì ngược lại.
4
Ta có $5 - 8 = -3$ . Theo quy ước % của Python, $(-3) \bmod 13 = 10$ (vì Python luôn trả kết quả không âm khi modulo dương). Kiểm tra: $13 \times (-1) + 10 = -3$ , đúng. Vậy tru_mod(5, 8, 13) = 10.
Ta có $5 - 8 = -3$. Theo quy ước `%` của Python, $(-3) \bmod 13 = 10$ (vì Python luôn trả kết quả không âm khi modulo dương). Kiểm tra: $13 \times (-1) + 10 = -3$, đúng. Vậy `tru_mod(5, 8, 13) = 10`.

Cộng, trừ, nhân từng cặp số là một chuyện; cộng dồn một DÃY số dài lại là chuyện khác — đặc biệt khi các số trong dãy đã gần tới $10^9$ , một quy mô rất thường gặp trong đề HSG QG.

Cộng, trừ, nhân từng cặp số là một chuyện; cộng dồn một DÃY số dài lại là chuyện khác — đặc biệt khi các số trong dãy đã gần tới $10^9$, một quy mô rất thường gặp trong đề HSG QG.

Ví dụ

Ví dụ 2 — Tổng một dãy số theo modulo, và vì sao Python không cần kiểu 64-bit

1
Bài chuẩn cộng một dãy vài số nhỏ, không bao giờ vượt phạm vi kiểu số nguyên thông thường. Đề HSG QG cho dãy tới $n \le 10^6$ số, mỗi số cỡ $10^9$ — tổng thật có thể tới $10^{15}$ , và nếu bài yêu cầu nhân thêm một bước nữa, kết quả trung gian dễ vượt xa phạm vi 64-bit của C++.
Bài chuẩn cộng một dãy vài số nhỏ, không bao giờ vượt phạm vi kiểu số nguyên thông thường. Đề HSG QG cho dãy tới $n \le 10^6$ số, mỗi số cỡ $10^9$ — tổng thật có thể tới $10^{15}$, và nếu bài yêu cầu nhân thêm một bước nữa, kết quả trung gian dễ vượt xa phạm vi 64-bit của C++.
2
Cộng dồn từng phần tử, lấy % p ngay sau mỗi bước — không đợi cộng hết dãy rồi mới lấy dư một lần:
```
def tong_day_mod(day_so, p):
    """Cong don tung phan tu, lay % ngay sau moi buoc de gia tri trung gian
    khong bao gio phinh to."""
    tong = 0
    for x in day_so:
        tong = (tong + x) % p
    return tong
```
Cộng dồn từng phần tử, lấy `% p` ngay sau mỗi bước — không đợi cộng hết dãy rồi mới lấy dư một lần: ```python def tong_day_mod(day_so, p): """Cong don tung phan tu, lay % ngay sau moi buoc de gia tri trung gian khong bao gio phinh to.""" tong = 0 for x in day_so: tong = (tong + x) % p return tong ```
3
Xét $a = b = 99\,999\,999$ . Tích $a \times b = 9\,999\,999\,800\,000\,001$ — khoảng $10^{16}$ , vượt xa giới hạn kiểu 32-bit ( $2^{31}-1 = 2\,147\,483\,647$ ). Trong C++, nhân hai biến int (32-bit) ở đây sẽ tràn số và cho kết quả sai (thường là một số âm vô nghĩa) mà chương trình không hề báo lỗi — bắt buộc phải khai báo long long (64-bit). Trong Python, a * b luôn cho đúng $9\,999\,999\,800\,000\,001$ dù $a, b$ lớn cỡ nào, vì kiểu int của Python có độ dài tùy ý — đây là điều cần nói rõ khi bàn số học modulo bằng Python: tràn số không phải là mối lo, nhưng đề bài và thói quen thi đấu (tham chiếu C++) vẫn giả định nó là mối lo, nên kỷ luật lấy dư từng bước vẫn là chuẩn mực chung.
Xét $a = b = 99\,999\,999$. Tích $a \times b = 9\,999\,999\,800\,000\,001$ — khoảng $10^{16}$, vượt xa giới hạn kiểu 32-bit ($2^{31}-1 = 2\,147\,483\,647$). Trong C++, nhân hai biến `int` (32-bit) ở đây sẽ tràn số và cho kết quả sai (thường là một số âm vô nghĩa) mà chương trình không hề báo lỗi — bắt buộc phải khai báo `long long` (64-bit). Trong Python, `a * b` luôn cho đúng $9\,999\,999\,800\,000\,001$ dù $a, b$ lớn cỡ nào, vì kiểu `int` của Python có độ dài tùy ý — **đây là điều cần nói rõ khi bàn số học modulo bằng Python: tràn số không phải là mối lo, nhưng đề bài và thói quen thi đấu (tham chiếu C++) vẫn giả định nó là mối lo, nên kỷ luật lấy dư từng bước vẫn là chuẩn mực chung.**
4
Với dãy $x=[12,9,7,5,20,33]$ và $p=13$ , cộng dồn TỔNG LŨY KẾ với từng số hạng mới, lấy dư ngay sau mỗi lần cộng: bắt đầu tổng $=0$ ; cộng $x_1=12$ : $0+12=12$ ; cộng $x_2=9$ : $12+9=21 \to 21\bmod 13=8$ ; cộng $x_3=7$ : $8+7=15 \to 15\bmod 13=2$ ; cộng $x_4=5$ : $2+5=7$ ; cộng $x_5=20$ : $7+20=27 \to 27\bmod 13=1$ ; cộng $x_6=33$ : $1+33=34 \to 34\bmod 13=8$ . Vậy tổng dãy modulo 13 bằng $8$ — kiểm tra: tổng thật $12+9+7+5+20+33=86$ , và $86\bmod 13=8$ , khớp.
Với dãy $x=[12,9,7,5,20,33]$ và $p=13$, cộng dồn TỔNG LŨY KẾ với từng số hạng mới, lấy dư ngay sau mỗi lần cộng: bắt đầu tổng $=0$; cộng $x_1=12$: $0+12=12$; cộng $x_2=9$: $12+9=21 \to 21\bmod 13=8$; cộng $x_3=7$: $8+7=15 \to 15\bmod 13=2$; cộng $x_4=5$: $2+5=7$; cộng $x_5=20$: $7+20=27 \to 27\bmod 13=1$; cộng $x_6=33$: $1+33=34 \to 34\bmod 13=8$. Vậy tổng dãy modulo 13 bằng $8$ — kiểm tra: tổng thật $12+9+7+5+20+33=86$, và $86\bmod 13=8$, khớp.

Bước 1: cộng x1=12, tổng lũy kế mod 13 = 12

Bước 3: cộng đến x3=7, tổng lũy kế mod 13 = 2

Bước 6: cộng hết dãy, tổng lũy kế mod 13 = 8 (đáp số cuối)

Mở rộng dành cho HSG

Cộng, trừ, nhân modulo đúng với MỌI modulo dương $p$ — không cần $p$ nguyên tố. Nhưng phép CHIA modulo (hai bài tiếp theo) lại khác hẳn: không phải số nào cũng có “nghịch đảo” để chia cho, và khi $p$ không nguyên tố, một số $a$ có thể hoàn toàn không chia được. Đây là lý do gần như mọi modulo trong đề HSG QG là số nguyên tố — thường là $p = 10^9+7$ .

Bẫy thường gặp

Ba lỗi hay gặp: quên lấy % p ngay sau phép NHÂN (chỉ nhớ lấy sau phép cộng) — hai số gần $10^9$ nhân nhau đã cỡ $10^{18}$ , và nếu còn một bước nhân nữa trước khi lấy dư, con số phình to không kiểm soát, chương trình vẫn ra đúng kết quả trong Python nhưng chạy chậm hẳn vì nhân số rất lớn tốn thời gian; nhầm rằng $a \bmod p$ luôn nhỏ hơn cả $a$ lẫn $p$ — nó chỉ đảm bảo nằm trong $[0, p)$ , không nói gì thêm về so sánh với $a$ ; và mang nguyên si thói quen C++ “phải cộng thêm p sau phép trừ” sang Python — thừa nhưng không sai, chỉ là không cần thiết.

Ba lỗi hay gặp: quên lấy `% p` ngay sau phép NHÂN (chỉ nhớ lấy sau phép cộng) — hai số gần $10^9$ nhân nhau đã cỡ $10^{18}$, và nếu còn một bước nhân nữa trước khi lấy dư, con số phình to không kiểm soát, chương trình vẫn ra đúng kết quả trong Python nhưng chạy chậm hẳn vì nhân số rất lớn tốn thời gian; nhầm rằng $a \bmod p$ luôn nhỏ hơn cả $a$ lẫn $p$ — nó chỉ đảm bảo nằm trong $[0, p)$, không nói gì thêm về so sánh với $a$; và mang nguyên si thói quen C++ “phải cộng thêm p sau phép trừ” sang Python — thừa nhưng không sai, chỉ là không cần thiết.

Luyện tập có hướng dẫn

Luyện tập độc lập

Thử thách

Ghi nhớ

Cộng, trừ, nhân modulo đều tuân theo một công thức duy nhất: lấy dư từng toán hạng trước, áp dụng phép toán, rồi lấy dư kết quả — đúng với mọi thứ tự và mọi modulo dương. Python không tràn số như C++, nhưng kỷ luật lấy dư ngay sau mỗi bước vẫn là chuẩn mực, vì nó giữ số nhỏ, chạy nhanh, và đúng với cách đề bài mong đợi.

Bài tiếp theo dùng lại đúng phép nhân modulo này để giải quyết một câu hỏi khác: tính $a^n \bmod p$ khi $n$ lớn tới $10^{18}$ — nhân liên tiếp $n$ lần là bất khả thi, cần một kỹ thuật nhanh hơn hẳn.