Momo's Blog

Talk is cheap. Show me the code.

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?

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ố 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ố.

Tại sao lại dùng modulo?

Lý do rất đơn giản, để tránh được việc số cần tính trở nên quá lớn. Đây là một bước nhằm đơn giản hoá bài toán, giúp chúng ta có thể tập trung toàn bộ vào việc thiết kế và tìm gia thuật toán, thay vì loanh quanh implement các phép toán đối với số lớn.

1000000007 là một số đủ lớn để các phép toán vừa trở nên đơn giản lại không bị tràn số. Cụ thể:

  • Phép cộng:
  • Phép trừ:
  • Phép nhân: . Chú ý một điều là fit 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ố.
  • Phép chia: Tại đây nảy sinh vấn đề, đó là lý do tại sao người ta chọn modulo là số nguyên tố, ta sẽ nói rõ hơn ở bên dưới
  • Phép luỹ thừa:

Tại sao lại dùng số nguyên tố?

Bởi vì 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í dụ như khi tính nghịch đảo theo modulo trong phép toán modulo đối với phân số chẳng hạn, ta sẽ chỉ có thể tính đơn giản khi m là số nguyên tố.

Với phép chia, ta phải chú ý một điều là:

biểu thức đúng phải là:

trong đó là nghịch đảo 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 toán học là . Đây là phần kiến thức khá quan trọng 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 ? Đây chính là lúc số nguyên tố thể hiện vai trò. Ta có:

khi và chỉ khi m và b là nguyên tố cùng nhau.

Vì thế khi m là số nguyên tố như 10^9+7 thì nó sẽ đủ lớn làm cho phép toán trên trở nên đúng trong phạm vi số nguyên.

Kết luận

Tóm lại, con số 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. Về thực chất thì các số nguyên tố đủ lớn trong phạm vi đều có thể thoả mãn, nhưng có lẽ là một số có cách viết “thuận mắt” và đẹp đẽ nhất.

Tham khảo