Đây là bản xem thử. Phiên bản đầy đủ trong ứng dụng có bài tập, AI chấm ngay và theo dõi tiến độ học.
Bài học
Số nguyên trong Python và số học modulo
Mục tiêu bài học
Sau bài này, em tính đúng một biểu thức số học rất lớn theo modulo — kiểu bài "in kết quả chia dư cho $10^9+7$" quen thuộc trong đề HSG — bằng cách lấy dư ngay sau **từng bước tính**, thay vì đợi tính xong toàn bộ biểu thức rồi mới lấy dư một lần.
Cần nhớ trước
Em cần nhớ lại: kiểu `int` trong Python, hai toán tử `//` (chia lấy phần nguyên) và `%` (chia lấy số dư), khái niệm giai thừa $n!$, và vòng lặp `for` cơ bản — tất cả đã học ở khóa nền tảng Lớp 10.
**So với mức chuẩn:** đề chuẩn Lớp 10 chỉ yêu cầu in trực tiếp một giá trị `int` nằm trong phạm vi vài trăm hay vài nghìn — Python tự lo phần còn lại vì số nguyên trong Python không giới hạn độ lớn (arbitrary precision), khác hẳn nhiều ngôn ngữ lập trình khác. Đề HSG lại thường cho những phép tính mà đáp số đúng có hàng trăm nghìn chữ số (ví dụ $100000!$), và yêu cầu "in kết quả theo modulo $10^9+7$" — không phải vì Python tràn số, mà vì hai lý do thực tế: chấm bài cần một con số cố định để so sánh chính xác, và phép nhân trên số càng lớn thì càng tốn thời gian.
Bài toán mở đầu — 100000! có bao nhiêu chữ số?
Em đã biết $20! = 2432902008176640000$ — con số này đã có 19 chữ số. Nếu $n$ tăng lên $100000$, $n!$ sẽ có tới gần nửa triệu chữ số. Python vẫn tính được con số khổng lồ đó không hề sai một chữ số nào, nhưng nếu đề chỉ hỏi "$100000!$ chia $10^9+7$ dư bao nhiêu", việc tính ra toàn bộ con số nửa-triệu-chữ-số rồi mới lấy dư là một sự lãng phí — vừa chậm, vừa không cần thiết.
Ý tưởng cốt lõi — lấy dư ngay sau mỗi phép nhân
Chìa khóa nằm ở một tính chất của phép chia lấy dư: với mọi số nguyên $a, b$ và modulo dương $p$, ta luôn có $(a \times b) \bmod p = ((a \bmod p) \times (b \bmod p)) \bmod p$. Nói cách khác, muốn biết phần dư của một tích, em không cần biết chính xác cả tích — chỉ cần giữ phần dư của từng thừa số qua mỗi bước là đủ. Áp dụng vào giai thừa: thay vì nhân dồn `r = r * i` rồi lấy dư ở cuối, ta lấy dư `r = (r * i) % MOD` ngay sau mỗi vòng lặp — `r` không bao giờ vượt quá `MOD`, nên mỗi phép nhân tiếp theo luôn thao tác trên những số nhỏ.
Ví dụ
Ví dụ 1 — Cơ chế lấy dư từng bước qua một trường hợp nhỏ ($5!$ mod 97)
1
Đề chuẩn Lớp 10 chỉ dừng ở việc in $5! = 120$ rồi thôi. Ở đây đề hỏi $5! \bmod 97$, và với $n$ lớn ta không thể tính hết $n!$ rồi mới lấy dư — nên trước khi làm với số lớn, ta cần chắc chắn cơ chế "lấy dư từng bước" cho ra đúng kết quả với một trường hợp nhỏ, kiểm tra được bằng tay.
2
Dùng đúng tính chất vừa nêu: r = (r * i) % 97 sau mỗi vòng lặp i, với r khởi tạo bằng 1.
Tính trực tiếp: $5! = 120$, và $120 = 1 \times 97 + 23$ nên $120 \bmod 97 = 23$ — khớp đúng với `r` sau vòng lặp. Vậy lấy dư từng bước hay lấy dư một lần ở cuối đều cho cùng một kết quả.
5
Ta có công thức $(a \times b) \bmod p = ((a \bmod p) \times (b \bmod p)) \bmod p$ với mọi $a, b$ nguyên và $p$ nguyên dương. Do đó vòng lặp
```python
def factorial_mod(n, mod):
r = 1
for i in range(1, n + 1):
r = (r * i) % mod
return r
```
gọi `factorial_mod(5, 97)` cho ra `r = 23` sau bước cuối, trùng với vết chạy ở trên. Vậy $5! \bmod 97 = 23$.
Mỗi ô là một vòng lặp — r không bao giờ vượt quá 97, dù kết quả cuối (5! = 120) lớn hơn modulo.
Cơ chế trên đúng với modulo nhỏ (97) hay modulo thật trong đề HSG ($10^9+7$, một số nguyên tố lớn quen thuộc) — chỉ khác nhau về độ lớn của $p$, không khác gì về cách làm. Ta thử áp dụng với $n$ lớn hơn nhiều.
Ví dụ
Ví dụ 2 — $n! \bmod (10^9+7)$ khi $n$ rất lớn ($n = 100000$)
1
$100000!$ có gần nửa triệu chữ số. Python vẫn tính được đầy đủ nhờ số nguyên không giới hạn, nhưng nếu đề chỉ cần phần dư theo $10^9+7$, tính ra toàn bộ con số khổng lồ đó rồi mới lấy dư là lãng phí thời gian không cần thiết.
2
Dùng đúng hàm `factorial_mod` ở Ví dụ 1, chỉ đổi modulo thành $10^9+7$ và $n$ thành $100000$ — `r` luôn ở trong khoảng $[0, 10^9+6]$ suốt vòng lặp, không bao giờ phình to.
3
MOD = 10**9 + 7
print(factorial_mod(100000, MOD)) # 457992974
4
Với $n=20$ (số nhỏ), Python tính trọn vẹn $20! = 2432902008176640000$, và $2432902008176640000 \bmod (10^9+7) = 146326063$. Gọi `factorial_mod(20, MOD)` cũng ra đúng $146326063$ — hai cách tính trùng khớp, nên tin tưởng được cách lấy dư từng bước khi $n$ lớn tới mức Python không còn tiện tính trọn vẹn.
5
Với $n$ càng lớn, phép nhân trên số nguyên khổng lồ càng chậm dần (số chữ số của kết quả cứ tăng theo từng vòng lặp), trong khi lấy dư mỗi bước giữ `r` luôn nhỏ hơn $10^9+7$ — mỗi phép nhân tốn thời gian gần như không đổi suốt vòng lặp.
6
Ta có $(a \times b) \bmod p = ((a \bmod p)(b \bmod p)) \bmod p$, nên lấy dư sau mỗi vòng lặp không làm thay đổi kết quả cuối, chỉ thay đổi độ lớn của các số trung gian. Do đó `factorial_mod(100000, 10**9+7)` cho kết quả đúng bằng $100000! \bmod (10^9+7)$. Vậy $100000! \bmod (10^9+7) = 457992974$.
Đo thực tế trên một lần chạy: không lấy dư mất khoảng 62 ms (số kết quả có 77338 chữ số), lấy dư mỗi bước chỉ khoảng 1 ms. Con số chính xác đổi theo từng máy, nhưng khoảng cách luôn rất lớn vì phép nhân trên số nguyên phình to chậm dần theo số chữ số.
Vì sao lấy dư không làm sai kết quả — nhìn qua một tổng
Cùng một tính chất modulo áp dụng được cho cả phép cộng: $(a+b) \bmod p = ((a \bmod p) + (b \bmod p)) \bmod p$. Ta kiểm chứng bằng một bài toán khác — tính tổng bình phương các số từ 1 đến 1000 theo modulo $10^9+7$.
Ví dụ
Ví dụ 3 — Vì sao lấy dư từng bước luôn cho kết quả đúng (chứng minh ngắn)
1
Chứng minh $(a \times b) \bmod p = ((a \bmod p)(b \bmod p)) \bmod p$, rồi áp dụng tính $S = \sum_{i=1}^{1000} i^2 \bmod (10^9+7)$ bằng cách cộng dồn và lấy dư ngay sau mỗi số hạng.
2
Đặt $a = k_1 p + r_1$, $b = k_2 p + r_2$ với $r_1 = a \bmod p$, $r_2 = b \bmod p$.
3
$a \times b = k_1 k_2 p^2 + k_1 p r_2 + k_2 p r_1 + r_1 r_2$. Ba số hạng đầu đều chứa thừa số $p$ nên chia hết cho $p$; chỉ còn $r_1 r_2$ quyết định phần dư.
4
Suy ra $(a \times b) \bmod p = (r_1 \times r_2) \bmod p = ((a \bmod p)(b \bmod p)) \bmod p$ — đúng như cần chứng minh. Lập luận với phép cộng cũng tương tự (bỏ số hạng $r_1 r_2$, thay bằng $r_1+r_2$).
5
def sum_squares_mod(n, mod):
s = 0
for i in range(1, n + 1):
s = (s + i * i) % mod
return s
print(sum_squares_mod(1000, 10**9 + 7)) # 333833500
6
Tổng thật $\sum_{i=1}^{1000} i^2 = \dfrac{1000 \times 1001 \times 2001}{6} = 333833500$ — nhỏ hơn $10^9+7$ nên phần dư trùng khớp chính xác với tổng thật, không bị "cắt bớt" gì cả. Tính trực tiếp `sum(i*i for i in range(1,1001)) % (10**9+7)` cũng ra đúng $333833500$, khớp với cách cộng dồn lấy dư từng bước.
7
Ta có $(a \times b) \bmod p = ((a \bmod p)(b \bmod p)) \bmod p$ (chứng minh ở trên), và lập luận tương tự cho phép cộng. Do đó cộng dồn và lấy dư sau mỗi số hạng trong vòng lặp không làm sai tổng. Vậy $\sum_{i=1}^{1000} i^2 \bmod (10^9+7) = 333833500$.
Bẫy thường gặp
Ba lỗi hay gặp: lấy dư chỉ ở bước cuối cùng thay vì từng bước — trong Python kết quả vẫn đúng (không tràn số), nhưng chương trình chạy chậm hẳn đi vì phải nhân trên những số ngày càng lớn; nhầm tưởng phép chia cũng lấy dư trực tiếp được như nhân và cộng — $(a \mathbin{/} b) \bmod p \ne (a \bmod p) \mathbin{/} (b \bmod p)$, muốn "chia dưới modulo" đúng cách cần một kỹ thuật khác (nghịch đảo modulo) nằm ngoài phạm vi bài này; và quên rằng phép trừ dưới modulo trong Python luôn cho kết quả không âm (khác một số ngôn ngữ khác, nơi phải cộng thêm $p$ trước khi lấy dư nếu kết quả trừ ra âm).
Luyện tập có hướng dẫn
Luyện tập độc lập
Thử thách
Tóm tắt
Python không tràn số, nhưng phép nhân trên số nguyên khổng lồ vẫn tốn thời gian — đó là lý do thật sự để lấy dư ngay sau mỗi bước tính, chứ không phải để "tránh lỗi". Công thức $(a \times b) \bmod p = ((a \bmod p)(b \bmod p)) \bmod p$ (và tương tự với phép cộng) đảm bảo lấy dư sớm hay muộn đều cho cùng một kết quả — chỉ khác nhau ở tốc độ và độ lớn của các số trung gian.
Bài tiếp theo dùng chính kiểu số nguyên này để giải một bài toán số học kinh điển khác: tìm ước chung lớn nhất của hai số bằng thuật toán Euclid — nhanh hơn hẳn cách liệt kê ước quen thuộc.
Sau bài này, em tính đúng một biểu thức số học rất lớn theo modulo — kiểu bài "in kết quả chia dư cho 109+7" quen thuộc trong đề HSG — bằng cách lấy dư ngay sau từng bước tính, thay vì đợi tính xong toàn bộ biểu thức rồi mới lấy dư một lần.
Em cần nhớ lại: kiểu int trong Python, hai toán tử // (chia lấy phần nguyên) và % (chia lấy số dư), khái niệm giai thừa n!, và vòng lặp for cơ bản — tất cả đã học ở khóa nền tảng Lớp 10.
So với mức chuẩn: đề chuẩn Lớp 10 chỉ yêu cầu in trực tiếp một giá trị int nằm trong phạm vi vài trăm hay vài nghìn — Python tự lo phần còn lại vì số nguyên trong Python không giới hạn độ lớn (arbitrary precision), khác hẳn nhiều ngôn ngữ lập trình khác. Đề HSG lại thường cho những phép tính mà đáp số đúng có hàng trăm nghìn chữ số (ví dụ 100000!), và yêu cầu "in kết quả theo modulo 109+7" — không phải vì Python tràn số, mà vì hai lý do thực tế: chấm bài cần một con số cố định để so sánh chính xác, và phép nhân trên số càng lớn thì càng tốn thời gian.
Em đã biết 20!=2432902008176640000 — con số này đã có 19 chữ số. Nếu n tăng lên 100000, n! sẽ có tới gần nửa triệu chữ số. Python vẫn tính được con số khổng lồ đó không hề sai một chữ số nào, nhưng nếu đề chỉ hỏi "100000! chia 109+7 dư bao nhiêu", việc tính ra toàn bộ con số nửa-triệu-chữ-số rồi mới lấy dư là một sự lãng phí — vừa chậm, vừa không cần thiết.
Chìa khóa nằm ở một tính chất của phép chia lấy dư: với mọi số nguyên a,b và modulo dương p, ta luôn có (a×b)modp=((amodp)×(bmodp))modp. Nói cách khác, muốn biết phần dư của một tích, em không cần biết chính xác cả tích — chỉ cần giữ phần dư của từng thừa số qua mỗi bước là đủ. Áp dụng vào giai thừa: thay vì nhân dồn r = r * i rồi lấy dư ở cuối, ta lấy dư r = (r * i) % MOD ngay sau mỗi vòng lặp — r không bao giờ vượt quá MOD, nên mỗi phép nhân tiếp theo luôn thao tác trên những số nhỏ.
Ví dụ 1 — Cơ chế lấy dư từng bước qua một trường hợp nhỏ (5! mod 97)
Đề chuẩn Lớp 10 chỉ dừng ở việc in 5!=120 rồi thôi. Ở đây đề hỏi 5!mod97, và với n lớn ta không thể tính hết n! rồi mới lấy dư — nên trước khi làm với số lớn, ta cần chắc chắn cơ chế "lấy dư từng bước" cho ra đúng kết quả với một trường hợp nhỏ, kiểm tra được bằng tay.
Tính trực tiếp: 5!=120, và 120=1×97+23 nên 120mod97=23 — khớp đúng với r sau vòng lặp. Vậy lấy dư từng bước hay lấy dư một lần ở cuối đều cho cùng một kết quả.
Ta có công thức (a×b)modp=((amodp)×(bmodp))modp với mọi a,b nguyên và p nguyên dương. Do đó vòng lặp
def factorial_mod(n, mod):
r = 1
for i in range(1, n + 1):
r = (r * i) % mod
return r
gọi factorial_mod(5, 97) cho ra r = 23 sau bước cuối, trùng với vết chạy ở trên. Vậy 5!mod97=23.
Cơ chế trên đúng với modulo nhỏ (97) hay modulo thật trong đề HSG (109+7, một số nguyên tố lớn quen thuộc) — chỉ khác nhau về độ lớn của p, không khác gì về cách làm. Ta thử áp dụng với n lớn hơn nhiều.
Ví dụ 2 — n!mod(109+7) khi n rất lớn (n=100000)
100000! có gần nửa triệu chữ số. Python vẫn tính được đầy đủ nhờ số nguyên không giới hạn, nhưng nếu đề chỉ cần phần dư theo 109+7, tính ra toàn bộ con số khổng lồ đó rồi mới lấy dư là lãng phí thời gian không cần thiết.
Dùng đúng hàm factorial_mod ở Ví dụ 1, chỉ đổi modulo thành 109+7 và n thành 100000 — r luôn ở trong khoảng [0,109+6] suốt vòng lặp, không bao giờ phình to.
Với n=20 (số nhỏ), Python tính trọn vẹn 20!=2432902008176640000, và 2432902008176640000mod(109+7)=146326063. Gọi factorial_mod(20, MOD) cũng ra đúng 146326063 — hai cách tính trùng khớp, nên tin tưởng được cách lấy dư từng bước khi n lớn tới mức Python không còn tiện tính trọn vẹn.
Với n càng lớn, phép nhân trên số nguyên khổng lồ càng chậm dần (số chữ số của kết quả cứ tăng theo từng vòng lặp), trong khi lấy dư mỗi bước giữ r luôn nhỏ hơn 109+7 — mỗi phép nhân tốn thời gian gần như không đổi suốt vòng lặp.
Ta có (a×b)modp=((amodp)(bmodp))modp, nên lấy dư sau mỗi vòng lặp không làm thay đổi kết quả cuối, chỉ thay đổi độ lớn của các số trung gian. Do đó factorial_mod(100000, 10**9+7) cho kết quả đúng bằng 100000!mod(109+7). Vậy 100000!mod(109+7)=457992974.
Cùng một tính chất modulo áp dụng được cho cả phép cộng: (a+b)modp=((amodp)+(bmodp))modp. Ta kiểm chứng bằng một bài toán khác — tính tổng bình phương các số từ 1 đến 1000 theo modulo 109+7.
Chứng minh (a×b)modp=((amodp)(bmodp))modp, rồi áp dụng tính S=∑i=11000i2mod(109+7) bằng cách cộng dồn và lấy dư ngay sau mỗi số hạng.
Đặt a=k1p+r1, b=k2p+r2 với r1=amodp, r2=bmodp.
a×b=k1k2p2+k1pr2+k2pr1+r1r2. Ba số hạng đầu đều chứa thừa số p nên chia hết cho p; chỉ còn r1r2 quyết định phần dư.
Suy ra (a×b)modp=(r1×r2)modp=((amodp)(bmodp))modp — đúng như cần chứng minh. Lập luận với phép cộng cũng tương tự (bỏ số hạng r1r2, thay bằng r1+r2).
Tổng thật ∑i=11000i2=61000×1001×2001=333833500 — nhỏ hơn 109+7 nên phần dư trùng khớp chính xác với tổng thật, không bị "cắt bớt" gì cả. Tính trực tiếp sum(i*i for i in range(1,1001)) % (10**9+7) cũng ra đúng 333833500, khớp với cách cộng dồn lấy dư từng bước.
Ta có (a×b)modp=((amodp)(bmodp))modp (chứng minh ở trên), và lập luận tương tự cho phép cộng. Do đó cộng dồn và lấy dư sau mỗi số hạng trong vòng lặp không làm sai tổng. Vậy ∑i=11000i2mod(109+7)=333833500.
Ba lỗi hay gặp: lấy dư chỉ ở bước cuối cùng thay vì từng bước — trong Python kết quả vẫn đúng (không tràn số), nhưng chương trình chạy chậm hẳn đi vì phải nhân trên những số ngày càng lớn; nhầm tưởng phép chia cũng lấy dư trực tiếp được như nhân và cộng — (a/b)modp=(amodp)/(bmodp), muốn "chia dưới modulo" đúng cách cần một kỹ thuật khác (nghịch đảo modulo) nằm ngoài phạm vi bài này; và quên rằng phép trừ dưới modulo trong Python luôn cho kết quả không âm (khác một số ngôn ngữ khác, nơi phải cộng thêm p trước khi lấy dư nếu kết quả trừ ra âm).
Python không tràn số, nhưng phép nhân trên số nguyên khổng lồ vẫn tốn thời gian — đó là lý do thật sự để lấy dư ngay sau mỗi bước tính, chứ không phải để "tránh lỗi". Công thức (a×b)modp=((amodp)(bmodp))modp (và tương tự với phép cộng) đảm bảo lấy dư sớm hay muộn đều cho cùng một kết quả — chỉ khác nhau ở tốc độ và độ lớn của các số trung gian.