Tại sao trong các bài toán lập trình thường yêu cầu đưa ra modulo của 10^9+7?

Posted on:December 25, 2017

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+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ý do

Có 2 lý do cơ bản cho việc sử dụng modulo 109+710^9+7 :

  1. Để tránh các tính toán bị overflow.
  2. Để việc tính toán trở nên đơn giản hơn.

1. Để tránh việc tính toán bị overflow

Kiể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} - 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 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

109+710^9+7 là một số nguyên tố.

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 m

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 m

trong đó 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}.

Nếu trong tính toán thập phân B×1B=1B\times \frac{1}{B} = 1 thì theo modulo B×inv(B)≡1 mod mB \times inv(B) \equiv 1 \bmod m.

Ví dụ nghịch đảo của 2 trong tính toán thập phân là 12\frac{1}{2} vì 2×12=12\times \frac{1}{2} = 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 5. Vậy inv(2)=3 mod 5inv(2) = 3 \bmod 5.

Đâ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 m ? Đây chính là lúc số nguyên tố thể hiện vai trò.

Theo định lý nhỏ Fermat, nếu mm là một số nguyên tố và BB không chia hết cho mm thì ta có:

Bm−1≡1 mod mB^{m-1} \equiv 1 \bmod m

⇔B×Bm−2≡1 mod m\Leftrightarrow B \times B^{m-2} \equiv 1 \bmod m

⇔inv(B)=Bm−2 mod m\Leftrightarrow inv(B) = B^{m-2} \bmod m

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.

Kết luận

Tóm lại, con số 109+710^9+7 hay 1000000007 là một con số đặc biệt, nó đủ lớn, và nhằm mục đích đơn giản tính toán trong các bài toán lập trình.

Theo những gì đã chứng minh bên trên thì các số nguyên tố đủ lớn trong phạm vi 2302^{30} đều có thể thoả mãn, nhưng có lẽ 109+710^9+7 là một số có cách viết “thuận mắt” và đẹp đẽ nhất.

Tham khảo