输出中的模运算

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一致7.组合这些残差需要一些额外的知识(扩展欧几里德算法).对于这些特定的数字,我们可以繁殖的5 21剩余物和7 15剩余物得到4·21 + 1·15 = 99减少模35倍的产率29,其是答案(13残基²模数35).

如果模数是素数,则无法绕过算术.质量模量基本上要求对模数的平方数(或耗时的变通方法)使用算术运算,但复合模数允许在较小的数字上使用算术,最多只有模数的两倍.