在codechef和spoj问题中使用modulo 10 ^ 9 + 7的意义是什么？
我正在研究一个问题 ，需要输出为“每行输出答案模10 ^ 9 + 7”。 为什么modulo 10 ^ 9 + 7包含在问题中？ 它的意义是什么？
我不是在寻找问题的解决方案; 只有那个特定常数的重要性。
问题要求结果模数，因为替代方案，即要求浮点结果给出“高位”并询问整个结果，并不总是问题设定者正在寻找的。
- 这些问题往往是“发现并实施复发”的问题。 低位通常会告诉您发现的重复是否正确。
- 对于“高阶位”问题可能有一个特殊的技巧，可能基于一个聪明的分析近似。
- 人们不经常要求整体结果的原因是这需要参赛者实施大数字算术。
- 问题制定者通常不希望出于意外的伎俩，因为“错误的原因”来解决他们的问题。
10 ^ 9 + 7结束是一个非常好的选择。 这是一个“安全的素数”。 那意味着什么：
10 ^ 9 + 7是素数。 这意味着“中国剩余技巧”不适用; 如果你试图用两个质数的模数来模拟某些东西，比如pq，那么你可以用modulo p和modulo q来计算它，并使用扩展的欧几里德算法把它们放在一起。
不仅如此，10 ^ 9 + 6，即10 ^ 9 + 7-1，是素数的两倍。 因此，乘法模10 ^ 9 + 7的模数不会分解成小的东西，因此在那里不适用中文余数类似的技巧。
在一些问题中答案是非常大的数字，但强迫你实施长的arighmetics不是问题作者的目的。 因此他们要求你计算一些数字的答案，比如1000000007 ，所以你不必实现长算术，但答案仍然是可validation的。
如果它被要求以模10 ^ 9给出答案，你可以轻松掩盖这些位，但是为了使问题变得更加困难，选择10 ^ 9 + 7这样的数字