模10^9+7在编解码器和spoj问题中的意义是什么？

Question

我使用的是问题，它要求输出为“每一行输出的答案模块10^9+7”。为什么在问题中包括模块化10^9+7？它的意义是什么？

我不是在寻找这个问题的解决方案，只是这个常数的意义。

Answer 1

问题要求结果为模素数，因为选择，即要求提供“高阶位”的浮点结果和要求整个结果，并不总是问题设置者所要寻找的结果。

• 这些问题往往是“发现并实现反复出现的”问题。低阶位常常会告诉你你发现的重复是否正确。
• 对于“高阶位”问题，可能有一个特殊的技巧，也许是基于一个聪明的解析近似。
• 人们不经常要求获得全部结果的原因是，这要求参赛者实现大数运算。
• 问题策划者通常不想要意外的技巧来解决他们的问题，因为“错误的原因”。

最后，10^9+7是一个很好的选择。这是一个“安全的质数”。这意味着：

10^9+7是一个素数。这意味着“中国余数技巧”不适用；如果你试图计算出一个由两个素数组成的乘积，比如pq，那么你可以计算出模p和模q，并使用扩展的欧几里得算法将这些部分组合起来。

不仅如此，10^9+6，即10^9+7-1，是一个素数的两倍.因此，乘法群模10^9+7不会分解成小东西，因此没有中国式的类似余数的伎俩。

Answer 2

在某些问题中，答案是非常大的，但强迫您实现长时间的模拟并不是问题作者的目的。因此，他们要求你计算一些数字，比如1000000007，这样你就不需要实现长算术，但答案仍然是可验证的。

Answer 3

如果要求它以模10^9给出答案，您可以很容易地屏蔽这些位元，但为了使问题更加困难，可以选择10^9+7这样的数字。