math - 为什么编程竞赛想要以大素数为模的答案？

Question

我一直在尝试竞争性编程，并且已经看到很多次提到此声明了：


打印结果以109 + 7为模


现在我可以弄清楚，这是一种在处理非常大的数字时防止数字溢出的方法。但是它如何以及为什么起作用？如果有人能解释其背后的数学推理，我将不胜感激。

Answer 1

许多竞赛问题都要求您计算一些非常大的数字（例如，包含一些重复项的150个元素的序列的排列数）。许多编程语言本身并不支持任意精度算术，因此出于公平的考虑，对于那些竞赛，不要要求您提供确切的值是有意义的。那么，挑战就在于以下几点：如果您无法正确计算答案，那么竞赛网站如何知道何时获得正确答案？

最初吸引人的一种选择是仅以模的两倍大（例如232或264）取模，这样，使用C或C ++等语言工作的竞争对手就可以使用uint32_t或uint64_t来完成所有计算，让溢出正常发生，然后提交结果。但是，这不是特别理想。例如，假设问题如下：


计算10,000！


这个数字非常庞大，太大而无法容纳32位或64位无符号整数。但是，如果您只想以232或264为模，则可以使用以下程序：

#include <stdio.h>
int main() {
    puts("0");
}

原因是10,000！是至少5,000个偶数的乘积，因此其因子之一是25,000。因此，如果您只想对232或264做模运算，则实际上根本不需要计算它。您可以说结果是0 mod 232或264。

这里的问题是，如果得到的答案可以被这些数字中的任何一个整除，则工作模232或264是麻烦的。但是，如果我们对较大的素数求模，则此技巧将不起作用。例如，数字7,897,987是质数。如果您尝试计算10,000！ mod 7,897,987，那么您不能只说“答案为0”，因为没有一个数字会相乘成10,000！是7,897,987的除数。实际上，您必须做一些工作才能弄清楚这个数字是那个大素数的模。更一般而言，对大素数进行模运算通常需要您计算该大素数的实际答案模数，而不是使用数论技巧来完全跳过所有工作。

那么为什么要对1,000,000,007取模呢？该数字恰好是质数（因此最好用作模数），并且小于231-1，这是您可以在带符号的32位整数中容纳的最大可能值。这里的带符号性很好，因为在某些语言（例如Java）中，没有无符号整数类型，默认整数类型是32位带符号整数。这意味着您可以对1,000,000,007取模，而不必担心整数溢出。

总结一下：


对大素数进行模运算可能使您的程序产生正确的输出，实际上它进行了一些计算并且正确地进行了计算。
以1,000,000,007为模的工作方式允许多种语言使用其内置的整数类型来存储和计算结果。


希望这可以帮助！