算法题目中,遇到结果是大数时,为什么喜欢 MOD 10^x+7 ?

2019-04-13 15:11发布

参考:https://www.zhihu.com/question/26127900/answer/49049103

模一个大数和模一个质数可以减少冲突。 比如说如果所有的结果都是偶数…你模6就只可能出现0, 2, 4这三种情况…但模5还是可以出现2, 4, 1, 3这四(4=5-1)种情况的…
hash表如果是用取模的方法也要模一个大质数来减少冲突,出题人也会这样来 希望减少你“蒙对“的概率。 而模1e9+7又有一个很好的特点,就是相加不爆int,相乘不爆long long。

作者:李冠一
链接:https://www.zhihu.com/question/26127900/answer/32253465


在模素数p的情况下a*n(a非p的倍数)的循环节长为p,这是减少冲突的一个原因。另一方面模素数p的环是无零因子环,也就是说两个非p倍数的数相乘再模p不会是零(如果是0的话,在多个数连乘的情况下会大大增加冲突概率)。还有就是模素数所成的环还是个域,因而允许“除法”操作(乘以乘法逆元),模非素数就没有这个性质。
一般来说x的选取只要10^x+7保证比初始输入数据的范围大就可以了。比如有些数据范围小的题为了避免用long long而把模数设定为10007。至于为什么要用10^x+7,大概是因为这种patten多为素数而又比较好记吧。

作者:匿名用户
链接:https://www.zhihu.com/question/26127900/answer/32261019