编程竞赛为什么要对答案取模一些大质数？

Question

我一直在尝试竞技编程，已经看到很多次出现了这个语句:

对10⁹ + 7 取模后输出结果

现在我可以理解这是一种在处理超大数时避免数字溢出的方法。但它是如何以及为什么起作用的？如果有人能解释一下背后的数学原理，我会很感激。

- Pawan

---

https://dev59.com/4nI95IYBdhLWcg3wvgh9 - gtgaxiola

@gtgaxiola- 我不确定那个问题在这里是否特别相关。我认为这里的问题是“为什么要使用模1,000,000,007？”而不是“如何对大数进行取模指数运算？” - templatetypedef

@templatetypedef 你说得对。学习如何做并不难。我想知道为什么要这样做。 - Pawan

Answer 1

许多竞赛题目要求你计算非常非常大的数字（比如，包含大量重复元素的150个元素序列的排列数）。许多编程语言不支持任意精度算术，因此从公平角度考虑，这些比赛不要求你提供确切值是有道理的。那么问题来了：既然你无法准确计算，比赛网站怎么知道你有正确的答案呢？

一种看似可行的选择是，只要求你算出模某个大的二的幂（比如2的32次方或2的64次方）的余数。这样，在像C或C++这样的语言中工作的竞赛者可以使用uint32_t或uint64_t等数据类型进行所有计算，让溢出正常发生，然后提交结果。然而，这并不是特别理想的。例如，假设问题是这样的：

“计算10,000!”

这个数字非常巨大，远远超过32位或64位无符号整数的表示范围。但是，如果你只想得到模2的32次方或2的64次方的答案，你可以使用这个程序：

#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取模允许大量编程语言使用内置整数类型来存储和计算结果。

希望这可以帮到你！

- templatetypedef

---

讲解得非常好，谢谢 :) - Pawan

@templatetypedef 为什么是10^9 + 7？为什么不能是2^31-1，它本身也是一个质数，或者是2,147,483,629？ - John Solomon

我认为这是因为选择一个小于INT_MAX的数字可以在阈值上方留出一点余地，以便人们可以超过限制而不触发整数溢出。请注意，2×（10^9 + 7）仍适合于整数。 - templatetypedef

使用这种方法时，有没有办法找出实际的答案？例如：在模M中，n的阶乘给出x，但n的实际值是y。我们能否通过x和M得到y？ - Ashutosh Singh

有无限多个数字在模M下留下余数x，因此如果没有任何其他外部信息，就无法仅从M和x中恢复y。 - templatetypedef

@JohnSolomon 当 M=10^9+7 时，它也让计算 (a+b) modulo M 变得容易，因为 2M 仍然适合于 int，因此可以保证 (a+b) 不会溢出。否则，我们必须像 ((long long)(a) + b) % M 一样明确地强制转换，或将 a 和 b 声明为 long long。由于几乎每个问题都涉及加法，这将使 int 几乎无法使用。 - Madhuchhanda Mandal