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

Question

我一直在测试竞争性编程的水域,我已经看过很多次提到的这个陈述:

打印结果模10 ⁹ + 7

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

Answer 1

许多比赛问题要求您计算一些非常非常大的数字(例如,包含大量重复数据的150个元素序列的排列数).许多编程语言本身并不支持任意精度算术,因此为了公平起见,这些竞赛不会向您询问确切的值是有意义的.接下来的挑战如下:如果您无法准确计算出竞赛网站,那么竞赛网站何时能够得到正确答案？

一个最初吸引人的选择是仅仅要求以两个大功率(例如,2 ³²或2 ⁶⁴)为模的答案,以便使用C或C++等语言的竞争对手可以只使用uint32_t或uint64_t进行所有计算,让溢出正常发生,然后提交结果.然而,这不是特别理想的.例如,假设问题如下:

计算10,000!

这个数字非常巨大,而且太大而不适合32位或64位无符号整数.但是,如果您只想获得模数为2 ³²或2 ⁶⁴的答案,则可以使用此程序:

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

原因是10,000!是至少5,000个偶数的乘积,因此其中一个因子是2 ^5,000.因此,如果您只想要以2 ³²或2 ⁶⁴为模的答案,则实际上根本不需要计算它.你可以说结果是0 mod 2 ³²或2 ⁶⁴.

这里的问题是,如果得到的答案可以被这些数字中的任何一个完全整除,则工作模2 ³²或2 ⁶⁴是很麻烦的.但是,如果我们以大质数为模,那么这个技巧就不行了.例如,数字7,897,987是素数.如果你试图计算10,000!mod 7,897,987,那么你不能只说"答案是0",因为没有数字在10,000中相乘!是7,897,987的除数.你实际上必须做一些工作来弄清楚这个数字是什么模数大的素数.更一般地说,以大质数为模的工作通常需要你计算以大质数为模的实际答案,而不是使用数论的技巧来完全跳过所有的工作.

那么为什么工作模数为1,000,000,007？这个数字恰好是素数(因此最好用作模数)并且它小于2 ³¹ - 1,这是您可以在有符号的32位整数中拟合的最大可能值.签名在这里很好,因为在某些语言(如Java)中没有无符号整数类型,默认整数类型是32位有符号整数.这意味着您可以在不冒整数溢出的情况下工作模数1,000,000,007.

总结一下:

• 如果你的程序生成正确的输出,那么它可能会模拟一个大的素数,它实际上做了一些计算并正确地做了.
• 使用模数1,000,000,007允许大量语言使用其内置整数类型来存储和计算结果.

希望这可以帮助!