Modulo 10^9 + 7 là gì
Sao chép dữ liệu ví dụ trong bảng sau đây và dán vào ô A1 của một bảng tính Excel mới. Để công thức hiển thị kết quả, hãy chọn chúng, nhấn F2 và sau đó nhấn Enter. Nếu cần, bạn có thể điều chỉnh độ rộng cột để xem tất cả dữ liệu. Cuối cùng, chúng ta đã có kết quả vòng 1 - vòng loại ý tưởng của cuộc thi VMIG. Ngoài 40 dự án được tài trợ board và tài trợ tiền theo hoạch định ban đầu, chúng ta còn có thêm 10 dự án tiềm năng được tài trợ board (không được tài trợ tiền). Nếu bạn là người yêu thích competitive programming thì có lẽ bạn sẽ không lạ gì với con số này, nó xuất hiện thường xuyên trong các cuộc thi. Đến nỗi, bạn coi nó như một mặc định mà chẳng hề đề ý. Cho đến một ngày mình bắt gặp câu hỏi tại sao lại chọn con số 109+710^9+7109+7 này để tính modulo, mình ngớ người và vội vàng đi tìm đáp án. Đó thực sự là một con số đặc biệt: 1000000007, nó là một số nguyên tố. Nhưng đó chưa phải là tất cả, mình sẽ giải thích tại sao người ta lại dùng modulo và tại sao lại dùng số nguyên tố. Lý doCó 2 lý do cơ bản cho việc sử dụng modulo 109+710^9+7109+7 :
1. Để tránh việc tính toán bị overflowKiểu dữ liệu lớn nhất trong C/C++ là unsigned long long, có độ lớn 64 bit, tức là nó biểu diễn được các con số từ 0 cho tới 264−12^{64} - 1264−1. Nhưng trong nhiều bài toán ta cần phải tính toán các kết quả lớn hơn rất nhiều con số này, do đó ta cần làm nhỏ việc tính toán đi cho phù hợp với kiểu dữ liệu của chúng ta, đó chính là lý do của việc sử dụng phép tính modulo. Điều này giúp chúng ta có thể tập trung toàn bộ vào việc thiết kế và tìm kiếm thuật toán, thay vì loanh quanh implement các phép toán đối với số lớn. Và 1000000007 là một số đủ lớn để sau khi tính modulo, phép toán vừa trở nên đơn giản lại không bị tràn số. Cụ thể:
Chú ý một điều là (109+7)2(10^9+7)^2(109+7)2 vừa đủ 63 bits, nghĩa là phù hợp với kiểu dữ liệu long long, vì thế ta hoàn toàn có thể nhân mà không lo tràn số.
2. Để việc tính toán trở nên đơn giản hơn
Rất nhiều phép toán trở nên đơn giản hơn khi làm việc với số nguyên tố. Với phép chia, ta phải chú ý một điều là: AB mod m ≠ A mod mB mod m mod m\frac{A}{B}\bmod m~~~~~ \not = ~~~~~\frac{A\bmod m}{B\bmod m}\bmod mBAmodm = BmodmAmodmmodm biểu thức đúng phải là: AB mod m=(A mod m×inv(B) mod m+m) mod m\frac{A}{B}\bmod m = (A\bmod m \times inv(B)\bmod m + m)\bmod mBAmodm=(Amodm×inv(B)modm+m)modm trong đó inv(B)inv(B)inv(B) là nghịch đảo theo modulo m của B. Ta lưu ý ở đây là nghịch đảo theo modulo (modular multiplicative inverse), chứ không phải nghịch đảo đơn thuần trong tính toán thập phân là 1B\frac{1}{B}B1. Nếu trong tính toán thập phân B×1B=1B\times \frac{1}{B} = 1B×B1=1 thì theo modulo B×inv(B)≡1 mod mB \times inv(B) \equiv 1 \bmod mB×inv(B)≡1modm. Ví dụ nghịch đảo của 2 trong tính toán thập phân là 12\frac{1}{2}21 vì 2×12=12\times \frac{1}{2} = 12×21=1. Nhưng nghịch đảo theo modulo 5 của 2 sẽ là 3 vì 2×3=6≡1 mod 52 \times 3 = 6 \equiv 1 \bmod 52×3=6≡1mod5. Vậy inv(2)=3 mod 5inv(2) = 3 \bmod 5inv(2)=3mod5. Đây là phần kiến thức khá quan trọng, và được sử dụng rất nhiều trong mã hoá, các bạn có thể tự tìm hiểu thêm theo link trên. Vậy làm thế nào để tính inv(B) mod minv(B)\bmod minv(B)modm ? Đây chính là lúc số nguyên tố thể hiện vai trò. Theo định lý nhỏ Fermat, nếu mmm là một số nguyên tố và BBB không chia hết cho mmm thì ta có: Bm−1≡1 mod mB^{m-1} \equiv 1 \bmod mBm−1≡1modm ⇔B×Bm−2≡1 mod m\Leftrightarrow B \times B^{m-2} \equiv 1 \bmod m⇔B×Bm−2≡1modm ⇔inv(B)=Bm−2 mod m\Leftrightarrow inv(B) = B^{m-2} \bmod m⇔inv(B)=Bm−2modm Bằng phép biến đổi này ta đã chuyển modulo của phép chia trở về modulo của phép nhân và có thể tính toán một cách đơn giản. |
