Chuyển tới nội dung chính

Toán cho lập trình (GCD, số nguyên tố, số học modular)

Bạn sẽ học được gì

Một nhúm công cụ toán xuất hiện đi xuất hiện lại trong lập trình thi đấu và đời thực: ước chung lớn nhất (GCD) bằng thuật toán Euclid, bội chung nhỏ nhất (LCM), sàng Eratosthenes để tìm mọi số nguyên tố trong nháy mắt, và số học modular — cách "đồng hồ" để giữ số không tràn, kèm lũy thừa mod nhanh chạy trong O(log n).

1. Trực quan: GCD là "viên gạch lớn nhất lát kín hai cạnh"​

Bạn có một mảnh sàn 12 × 8. Muốn lát bằng những viên gạch vuông to nhất mà không cắt viên nào. Cạnh viên gạch lớn nhất chính là GCD(12, 8) = 4.

Thuật toán Euclid dựa trên một quan sát đẹp: gcd(a, b) = gcd(b, a mod b). Trực giác: bất kỳ số nào chia hết cả a và b thì cũng chia hết phần dư a mod b. Ta cứ thay số lớn bằng phần dư, bài toán nhỏ dần cho tới khi một số về 0 — số còn lại là đáp án.

   gcd(48, 36)
   48 mod 36 = 12   ->  gcd(36, 12)
   36 mod 12 =  0   ->  gcd(12,  0) = 12

2. Bước qua: thuật toán Euclid​

🐞 gcd(48, 36) bằng EuclidBước 1/5
1a = 48
2b = 36
3while b != 0:
4  a, b = b, a % b
5ket_qua = a
Biến tại bước này
a48
👉 Bắt đầu với a = 48.

3. Code: GCD và LCM​

Khi đã có GCD thì LCM gần như "miễn phí": lcm(a, b) = a * b / gcd(a, b). Để tránh tràn số, ta chia trước rồi mới nhân: a // gcd * b.

Đang tải trình chạy code…

Độ phức tạp của Euclid là O(log(min(a, b))) — cực nhanh, vì mỗi hai bước phần dư giảm ít nhất một nửa.

4. Sàng Eratosthenes: gạch tên mọi bội số​

Muốn liệt kê mọi số nguyên tố tới n? Đừng kiểm tra từng số một. Thay vào đó hãy gạch tên: viết tất cả số từ 2 tới n, lấy số nguyên tố nhỏ nhất chưa bị gạch (2), gạch mọi bội của nó (4, 6, 8...). Sang số chưa bị gạch tiếp theo (3), gạch mọi bội của 3... Số nào sống sót là số nguyên tố.

   2  3  4  5  6  7  8  9 10 11 12   (gach boi cua 2)
   2  3  X  5  X  7  X  9  X 11  X
   2  3     5     7     X    11      (gach boi cua 3: 9)
   con lai: 2 3 5 7 11  <- so nguyen to
Đang tải trình chạy code…

Hai mẹo tăng tốc: chỉ cần gạch tới i * i <= n (mọi hợp số nhỏ hơn đã bị gạch), và bắt đầu gạch từ i * i (các bội nhỏ hơn đã bị các số nguyên tố trước đó xử lý). Sàng chạy O(n log log n) — gần như tuyến tính.

5. Số học modular: toán trên mặt đồng hồ​

Trên đồng hồ 12 giờ, 10 giờ + 5 giờ = 3 giờ chứ không phải 15 — ta đã làm modulo 12. Số học modular giữ mọi số trong khoảng 0..m-1, rất hợp để chống tràn số khi đáp án khổng lồ (đề bài hay yêu cầu lấy kết quả mod 10^9 + 7).

Hai luật vàng cho phép "mod sớm, mod thường xuyên":

  • (a + b) mod m = ((a mod m) + (b mod m)) mod m
  • (a * b) mod m = ((a mod m) * (b mod m)) mod m

Nhưng 2^1000 mod m thì sao? Nhân 1000 lần thì chậm. Dùng lũy thừa mod nhanh (binary exponentiation): tách số mũ theo nhị phân, bình phương cơ số ở mỗi bước, chỉ nhân vào kết quả khi bit tương ứng bằng 1 → chỉ O(log n) phép nhân.

🐞 luy_thua_mod(3, 5, 100): tính 3^5 mod 100Bước 1/6
1def luy_thua_mod(co_so, mu, m):
2  kq = 1
3  co_so %= m
4  while mu > 0:
5      if mu & 1:
6          kq = kq * co_so % m
7      co_so = co_so * co_so % m
8      mu >>= 1
9  return kq
Biến tại bước này
kq1
mu5
👉 kq = 1. Mũ 5 = nhị phân 101.

6. Code: lũy thừa mod nhanh​

Đang tải trình chạy code…

Bẫy thường gặp: với n âm hoặc 0, đảm bảo vòng lặp xử lý đúng (mũ 0 → trả về 1). Trong Python, pow(co_so, mu, m) đã làm sẵn việc này và nên dùng cho code thật.

7. Mẫu nhận diện​

  • "Rút gọn phân số", "chu kỳ chung", "viên gạch lớn nhất" → GCD / LCM.
  • "Liệt kê / đếm số nguyên tố tới N", "phân tích thừa số nhanh" → sàng Eratosthenes.
  • "Kết quả rất lớn, lấy mod 10^9 + 7" → số học modular (mod sớm, mod thường xuyên).
  • "Tính a^b với b khổng lồ" → lũy thừa mod nhanh O(log b).

8. 🎮 Trò chơi: Toán nhanh​

🎮 Toán cho lập trìnhCâu 1/4· Điểm 0· 🔥 0

GCD bằng Euclid, sàng để tìm nguyên tố, lũy thừa mod nhanh. Tính nhẩm nhé!

In ra gì?

print(pow(3, 5, 100))

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Thuật toán Euclid dựa trên đẳng thức nào?
2. Vì sao trong số học modular ta "mod sớm, mod thường xuyên"?
3. Lũy thừa mod nhanh tính a^b mod m trong thời gian?

10. Hoàn thành​

…

☑️ Tiếp theo: 3.6.3 — Tìm chuỗi con (KMP, Rabin-Karp) (so khớp mẫu trong văn bản).