Đồng dư và phép toán modulo

Mức độ: Cơ bản

Rất nhiều đề thi có câu: “in ra kết quả sau khi chia lấy dư cho 10⁹ + 7”. Lý do là đáp số thật quá lớn (ví dụ 1000! có 2568 chữ số), không biến nào lưu được. Bài này giúp các bạn tính đúng số dư đó mà không bao giờ phải tính ra con số khổng lồ.

Các bạn nên học trước bài Phép chia có dư và chia hết.

Đồng dư là gì?

Hai số đồng dư theo modulo m nếu chúng có cùng số dư khi chia cho m. Viết:

a ≡ b (mod m)

Ví dụ 17 ≡ 2 (mod 5) vì 17 và 2 cùng chia 5 dư 2. Ngày thứ 100 và ngày thứ 2 tính từ một thứ Hai có cùng thứ vì 100 ≡ 2 (mod 7).

Cách nói khác: a ≡ b (mod m) khi a - b chia hết cho m.

Ba quy tắc quan trọng

Muốn biết số dư của một tổng, hiệu hay tích, chỉ cần số dư của từng số:

Phép toán	Quy tắc
Cộng	(a + b) % m = (a % m + b % m) % m
Nhân	(a × b) % m = ((a % m) × (b % m)) % m
Trừ	(a - b) % m = (a % m - b % m + m) % m

Vì sao đúng? Lấy m = 10, số dư chính là chữ số hàng đơn vị. Muốn biết chữ số tận cùng của 123 × 456, các bạn chỉ cần nhân 3 × 6 = 18, được chữ số 8. Các phần còn lại (120 × 456, 3 × 450) đều tận cùng bằng 0, không ảnh hưởng. Với m bất kỳ cũng vậy: phần chia hết cho m không làm thay đổi số dư.

Ở phép trừ, cộng thêm m là để kết quả không bị âm (xem số dư của số âm).

Lưu ý: không có quy tắc như vậy cho phép chia. Ví dụ (12 / 4) % 5 = 3, nhưng (12 % 5) / (4 % 5) = 2 / 4, không phải số nguyên. Chia theo modulo cần một công cụ khác (nghịch đảo modulo) sẽ học ở bài Lũy thừa nhanh.

Lấy dư sau mỗi bước

Tính n! % (10⁹ + 7): nhân dần từ 1 đến n, sau mỗi lần nhân thì lấy dư ngay. Theo quy tắc nhân, kết quả cuối cùng vẫn đúng, mà các số trung gian luôn nhỏ hơn 10⁹ + 7.

Python
C++

MOD = 10 ** 9 + 7
n = int(input())
gt = 1
for i in range(1, n + 1):
    gt = gt * i % MOD        # lấy dư ngay sau mỗi lần nhân
print(gt)                    # n = 1000000 in ra 641102369

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    long long gt = 1;
    for (int i = 1; i <= n; i++) {
        gt = gt * i % MOD;     // lấy dư ngay sau mỗi lần nhân
    }
    cout << gt << endl;        // n = 1000000 in ra 641102369
    return 0;
}

Vì sao C++ không bị tràn? gt luôn nhỏ hơn MOD (khoảng 10⁹), i không quá 10⁶, nên gt * i không quá 10¹⁵, vừa long long (tới khoảng 9,2 × 10¹⁸). Nhân hai số cùng nhỏ hơn MOD thì tích nhỏ hơn 10¹⁸, vẫn vừa.

Lưu ý:

Trong C++ phải dùng long long. Viết int gt thì gt * i bị tràn ngay.
Nếu hai số cần nhân chưa được lấy dư (ví dụ đều khoảng 10¹⁸), phải lấy dư từng số trước: (a % MOD) * (b % MOD) % MOD.
Python không bị tràn số nhưng vẫn nên lấy dư sau mỗi bước, nếu không các số phình to và chương trình chạy rất chậm.

Vì sao lại là 10⁹ + 7? Số này đủ lớn để đáp số ít bị “trùng”, đủ nhỏ để tích hai số dư vừa long long, và là số nguyên tố, một tính chất cần cho phép chia theo modulo.

Số dư của số rất lớn

Số có 10⁵ chữ số phải đọc dưới dạng xâu. Đọc từ trái sang phải, mỗi chữ số mới làm số cũ nhân 10 rồi cộng chữ số đó (1234 = 123 × 10 + 4). Áp dụng quy tắc cộng và nhân, chỉ cần giữ số dư:

số dư mới = (số dư cũ × 10 + chữ số) % m

Chạy tay 1234 % 7:

Chữ số	Phép tính	Số dư
1	(0 × 10 + 1) % 7	1
2	(1 × 10 + 2) % 7	5
3	(5 × 10 + 3) % 7	4
4	(4 × 10 + 4) % 7	2

1234 = 7 × 176 + 2. Đúng.

Đếm theo số dư

Nhiều bài hỏi “có bao nhiêu cặp có tổng chia hết cho k”. Thay vì thử mọi cặp, ta nhóm các số theo số dư khi chia cho k:

Hai số có tổng chia hết cho k khi tổng hai số dư bằng 0 hoặc bằng k.
Hai số có hiệu chia hết cho k khi chúng cùng số dư (đồng dư).

Ý thứ hai rất mạnh khi kết hợp với tổng tiền tố: một đoạn liên tiếp có tổng chia hết cho k khi hai tổng tiền tố ở hai đầu đoạn có cùng số dư (bài 13).

Luyện tập

Gồm 21 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. Cộng, trừ, nhân theo modulo

Bài 1. Tích hai số lớn

Nhập ba số nguyên dương a, b, m (a, b ≤ 10¹⁸, m ≤ 10⁹). In ra (a × b) % m.

Ví dụ: nhập 123456789 987654321 1000 thì in ra 269.

Kiểm tra: nhập 1000000000000000000 999999999999999999 1000000007.

Xem đáp số

2352

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

Bài 2. Giai thừa modulo

Nhập số nguyên dương n (n ≤ 10⁶). In ra n! % (10⁹ + 7).

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

Kiểm tra: nhập 1000000.

Xem đáp số

641102369

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

Bài 3. Tổng từ 1 đến n

Nhập hai số nguyên dương n, m (n ≤ 10¹⁸, m ≤ 10⁹). In ra (1 + 2 + … + n) % m.

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

Kiểm tra: nhập 1000000000000000000 1000000007.

Xem đáp số

1225

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

Bài 4. Tổng bình phương

Nhập số nguyên dương n (n ≤ 10⁶). In ra (1² + 2² + … + n²) % (10⁹ + 7).

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

Kiểm tra: nhập 1000000.

Xem đáp số

163183

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

Bài 5. Hiệu theo modulo

Nhập ba số nguyên dương a, b, m (a, b ≤ 10¹⁸, m ≤ 10⁹). In ra số dư không âm của a - b khi chia cho m.

Ví dụ: nhập 5 12 7 thì in ra 0.

Kiểm tra: nhập 3 1000000000000000000 1000000007.

Xem đáp số

999999961

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

Bài 6. Số Fibonacci modulo

Dãy Fibonacci: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). Nhập n (n ≤ 10⁶), in ra F(n) % (10⁹ + 7).

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

Kiểm tra: nhập 1000000.

Xem đáp số

918091266

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

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

Bài 7. Số dư của số rất lớn

Dòng đầu là số nguyên dương n có không quá 10⁵ chữ số. Dòng thứ hai là số nguyên dương m (m ≤ 10⁹). In ra n % m.

Ví dụ:

Nhập	In ra
`2026` `7`	`3`

Kiểm tra: nhập

123456789123456789123456789
1000000009

Xem đáp số

12345516

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

Bài 8. Hai số rất lớn đồng dư

Ba dòng lần lượt là hai số nguyên dương x, y (mỗi số không quá 10⁵ chữ số) và số nguyên dương m (m ≤ 10⁹). In ra YES nếu x ≡ y (mod m), ngược lại in ra NO.

Ví dụ:

Nhập	In ra
`2026` `5` `7`	`NO`

Kiểm tra: nhập

98765432109876543210
12345678901234567890
37

Xem đáp số

NO

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

Bài 9. Chia hết cho 11

Nhập số nguyên dương n có không quá 10⁵ chữ số. In ra YES nếu n chia hết cho 11, ngược lại in ra NO.

Ví dụ: nhập 121 thì in ra YES.

Kiểm tra: nhập 918273645546372819.

Xem đáp số

YES

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

Bài 10. Ghép các số từ 1 đến n

Viết liền các số 1, 2, 3, …, n thành một số rất lớn (ví dụ n = 12 được 123456789101112). Nhập n (n ≤ 10⁶), in ra số đó chia lấy dư cho 10⁹ + 7.

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

Kiểm tra: nhập 1000.

Xem đáp số

996345836

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

Bài 11. Số toàn chữ số 1

Nhập hai số nguyên dương n, m (n ≤ 10⁶, m ≤ 10⁹). In ra số gồm n chữ số 1 (111…1) chia lấy dư cho m.

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

Kiểm tra: nhập 1000000 1000000007.

Xem đáp số

545258758

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

Nhóm 3. Đếm theo số dư

Bài 12. Cặp có tổng chia hết cho k

Dòng đầu có hai số n, k (n ≤ 10⁵, k ≤ 10⁵). Dòng thứ hai có n số nguyên dương a₁, …, a_n (mỗi số không quá 10⁹). Đếm số cặp chỉ số i nhỏ hơn j mà a_i + a_j chia hết cho k.

Ví dụ:

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

Kiểm tra: nhập

7 4
3 7 5 1 9 11 4

Xem đáp số

9

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

Bài 13. Đoạn con có tổng chia hết cho k

Dòng đầu có hai số n, k (n ≤ 10⁵, k ≤ 10⁹). Dòng thứ hai có n số nguyên a₁, …, a_n (giá trị tuyệt đối không quá 10⁹). Đếm số đoạn liên tiếp (gồm ít nhất một số) có tổng chia hết cho k.

Ví dụ:

Nhập	In ra
`3 3` `1 2 3`	`3`

Kiểm tra: nhập

6 5
4 5 0 -2 -3 1

Xem đáp số

7

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

Bài 14. Số dư phổ biến nhất

Dòng đầu có hai số n, k (n ≤ 10⁵, k ≤ 10⁵). Dòng thứ hai có n số nguyên dương. Trong các số dư khi chia các số đó cho k, in ra số dư xuất hiện nhiều nhất và số lần xuất hiện. Nếu nhiều số dư cùng nhiều nhất thì chọn số dư nhỏ nhất.

Ví dụ:

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

Kiểm tra: nhập

8 5
12 25 7 40 33 18 3 10

Xem đáp số

0 3

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

Bài 15. Bội số toàn chữ số 1

Nhập số nguyên dương k (k ≤ 10⁶, k không chia hết cho 2 và 5). Tìm số nhỏ nhất gồm toàn chữ số 1 (1, 11, 111, …) chia hết cho k, in ra số chữ số của nó.

Ví dụ: nhập 7 thì in ra 6.

Kiểm tra: nhập 2027.

Xem đáp số

1013

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

Bài 16. Số chia các số dư cho trước

Dòng đầu là t (t ≤ 5). Mỗi dòng trong t dòng tiếp theo có hai số m, r (0 ≤ r nhỏ hơn m). Tích các m không quá 10⁶. Tìm số nguyên dương nhỏ nhất x sao cho x chia m dư r với mọi dòng. Nếu không có thì in ra -1.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

23

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

Nhóm 4. Vận dụng

Bài 17. Lũy thừa modulo

Nhập ba số nguyên dương a, b, m (a ≤ 10¹⁸, b ≤ 10⁶, m ≤ 10⁹). In ra a^b % m.

Ví dụ: nhập 3 20 1000 thì in ra 401.

Kiểm tra: nhập 2 1000000 1000000007.

Xem đáp số

235042059

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

Bài 18. Hai chữ số tận cùng của 2^n

Nhập số nguyên dương n (n ≤ 10⁶). In ra hai chữ số tận cùng của 2ⁿ (in đủ hai chữ số, ví dụ 04).

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

Kiểm tra: nhập 2026.

Xem đáp số

64

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

Bài 19. Leo cầu thang

Cầu thang có n bậc. Mỗi bước có thể leo 1, 2 hoặc 3 bậc. Nhập n (1 ≤ n ≤ 10⁶), in ra số cách leo hết cầu thang, chia lấy dư cho 10⁹ + 7.

Ví dụ: nhập 4 thì in ra 7.

Kiểm tra: nhập 1000.

Xem đáp số

509672692

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

Bài 20. Tổ hợp bằng tam giác Pascal

Nhập hai số nguyên n, k (0 ≤ k ≤ n ≤ 1000). In ra số cách chọn k đồ vật từ n đồ vật khác nhau, chia lấy dư cho 10⁹ + 7.

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

Kiểm tra: nhập 1000 500.

Xem đáp số

159835829

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

Bài 21. Tổng các tích từng cặp

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số nguyên dương, mỗi số không quá 10⁹. In ra tổng a_i × a_j với mọi cặp i nhỏ hơn j, chia lấy dư cho 10⁹ + 7.

Ví dụ:

Nhập	In ra
`4` `1 2 3 4`	`35`

Kiểm tra: nhập

5
1000000000 999999999 123456789 987654321 5

Xem đáp số

147995817

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