演算法題目中，遇到結果是大數時，為什麼喜歡 MOD 10^x+7 ?

01-05

題主說的10^x+7多半時候是1e9+7吧。

模一個大數和模一個質數可以減少衝突。

比如說如果所有的結果都是偶數…你模6就只可能出現0, 2, 4這三種情況…但模5還是可以出現2, 4, 1, 3這四(4=5-1)種情況的…

hash表如果是用取模的方法也要模一個大質數來減少衝突，出題人也會這樣來希望減少你「蒙對「的概率。

而模1e9+7又有一個很好的特點，就是相加不爆int，相乘不爆long long。

PS：另外，我覺得這其實也是一種文化……最初大家都用1e9+7這個大質數……後來就會有人獨出心裁要用1e8+7之類的…

糾正一下@李冠一的答案。在模素數p的情況下a*n（a非p的倍數）的循環節長為p,這是減少衝突的一個原因。另一方面模素數p的環是無零因子環,也就是說兩個非p倍數的數相乘再模p不會是零（如果是0的話,在多個數連乘的情況下會大大增加衝突概率）。還有就是模素數所成的環還是個域,因而允許「除法」操作（乘以乘法逆元）,模非素數就沒有這個性質。

一般來說x的選取只要10^x＋7保證比初始輸入數據的範圍大就可以了。比如有些數據範圍小的題為了避免用long long而把模數設定為10007。至於為什麼要用10^x＋7,大概是因為這種patten多為素數而又比較好記吧。

為什麼喜歡998244353呢~

歪個樓，有次TC比賽結果讓模1e9+9，然後讓Petr等眾神光榮的掛了……

因為如果mod簡單的數

理論上會增大演算法錯誤但是由於巧合恰好模出相等的數，而AC的概率

而1e9+7這個數是素數，相加不爆int，相乘不爆ll

這個問題分兩個層次

1. 為什麼要取模？

答：幾種可能

1 出題的無聊

2 結果的數值太大，常見數據類型無法表示，出題者為了省事（不想寫高精度表示）只好將結果映射到一個合理的區間之內。

3 使用hash表

2.為什麼要模10^x+7？

答：幾種可能

1 出題的無聊

2 10^x+7 有可能是個質數，而結果模質數的時候，餘數的"種類"最多。假如模一個合數的話，「種類」少了，不同的兩個數取模之後答案一樣的概率更大，可能更容易出現有些做題者的結果是錯的，但是取模之後仍然得到了正確的答案的情況。