c - 输出中的模运算

Question

在大多数假定程序输出非常大的编码竞赛中，通常指示将输出除以 10000007（或在这种情况下为素数）。取素数的意义是什么，因为在许多情况下，我发现与 100004 相同的数字（即不是素数）..？

Answer 1

使用素数有两个原因。一个原因是整数模素数形成一个数学域。领域中的算术以多种方式起作用，例如整数算术。这使得一个字段在某些竞赛问题中很有用，否则在某些情况下使用的序列可能会崩溃。某些算术可能会产生零、其他微不足道的结果或比期望更简单的结果，因为涉及的数字发生在模数的一个因子上，导致发生一些减少或消除。

另一个原因是迫使程序员处理一定大小的整数的算术运算。如果使用复合数，则可以使用其他技术，而不是求助于大整数的算术。

例如，假设我们想知道 13 ²以 35 为模，但我们只有一个非常小的处理器，无法处理三位数字，因此它无法计算 13 ² = 169。

嗯，35 = 5•7，并且 13 与 3 模 5 和 6 模 7 一致。我们可以计算这些余数的平方，而不是计算 13 的平方，这告诉我们 13 ²与 3 ² = 9 = 4 模 5 并且等于 6 ² = 36 = 1 模 7。组合这些残基需要一些额外的知识（扩展欧几里得算法）。对于这些特定的数字，我们可以将 5 的余数乘以 21，并将 7 的余数乘以 15，得到 4·21+1·15 = 99。减少模 35 得到 29，这就是答案（13 的余数²模 35)。

如果模数是素数，则这种算术规避是不可用的。素数模数本质上需要对数的算术使用直到模数的平方（或耗时的解决方法），但复合模数将允许对较小的数使用算术，最多只有模数的两倍。