取模 10^9+7

Posted by Xsp on February 2, 2018

算法题中通常会要求对 10^9+7 取模,来避免整数溢出的问题。其中10^9+7是一个比较大的质数。

原因如下:

  1. 为什么要取模?数据比较大时,避免整数溢出。
  2. 为什么要是质数?能够保证散列后的数尽量随机均匀分布。->延伸问题:散列函数取模为啥用质数?可以尽量避免冲突? ..没找到合适的答案。

参考: https://www.zhihu.com/question/20806796/answer/21359160 http://www.vvbin.com/?p=376 https://zhaox.github.io/algorithm/2015/06/29/hash https://www.geeksforgeeks.org/modulo-1097-1000000007/ https://codeaccepted.wordpress.com/2014/02/15/output-the-answer-modulo-109-7/ https://discuss.codechef.com/questions/1440/algorithm-to-find-inverse-modulo-m http://blog.csdn.net/liuchuo/article/details/51994215

  1. 这个取模的数要足够大

1000000009 也可以,只不过 可以把 1000000007 约定俗成的。