我正在研究一个问题 http://www.codechef.com/SEPT14/problems/CHEFLR它需要输出为“对于每行输出答案模 10^9+7”。为什么是模 10^9+7包含在问题中吗？其意义何在？
我不是在寻找问题的解决方案；仅该特定常数的意义。
问题要求对素数取模的结果，因为替代方案，即要求给出“高阶位”的浮点结果并要求整个结果，并不总是问题设置者正在寻找的。
- 这些问题往往是“发现并实施重复出现”的问题。低位通常会告诉您发现的递归是否正确。
- 对于“高阶位”问题可能有一个特殊的技巧，也许基于巧妙的分析近似。
- 人们通常不要求完整结果的原因是，这需要参赛者执行大数算术。
- 问题解决者通常不希望出于“错误的原因”而使用意想不到的技巧来解决他们的问题。
10^9+7 最终成为质数的一个不错的选择。这是一个“安全素数”。那意味着什么：
10^9+7 是质数。这意味着“中国余数技巧”不适用；如果你想计算出两个素数乘积的模数，比如 pq，那么你可以计算出模 p 和模 q，并使用扩展的欧几里得算法将各个部分组合在一起。
不仅如此，10^9+6，即10^9+7-1，是素数的两倍。因此，模 10^9+7 的乘法群不会分解为小东西，因此不适用类似中国余数的技巧。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
