最近在一道筆試題里看到了一個(gè)運(yùn)算結(jié)果很大的數(shù)，會(huì)超過(guò)所有類型的最大值，題目要求結(jié)果對(duì)10^9+7取模，上網(wǎng)搜索這個(gè)問(wèn)題的解決方法才發(fā)現(xiàn)這是面試中常有的問(wèn)題，所以記錄一下。

　　為什么要取模？是因?yàn)榻Y(jié)果不能用任何數(shù)字類型來(lái)存儲(chǔ)，用字符串又不方便運(yùn)算，所以要進(jìn)行取模操作。

　　那為什么是10^9+7?首先，10^9+7是一個(gè)足夠大的質(zhì)數(shù)，對(duì)于質(zhì)數(shù)求模操作可能得到的結(jié)果要遠(yuǎn)大于合數(shù)，有效避免了蒙中答案的概率。另外10^9+7有一個(gè)很好的特點(diǎn)，相加不超過(guò)int，相乘不超過(guò)longlong。

　　那么，代碼上應(yīng)該怎么解決呢？

　　很簡(jiǎn)單，這利用了同余定理。

同余定理：數(shù)論中的重要概念。給定一個(gè)正整數(shù)m，如果兩個(gè)整數(shù)a和b滿足a-b能夠被m整除，即(a-b)/m得到一個(gè)整數(shù)，那么就稱整數(shù)a與b對(duì)模m同余，記作a≡b(mod m)。對(duì)模m同余是整數(shù)的一個(gè)等價(jià)關(guān)系。

　　在代碼中，a,b相乘，對(duì)p取余，我們?nèi)%p作為a的同余數(shù)，b%p作為b的同余數(shù)，那么(a * b)%p = (a%p * b%p)%p，根據(jù)10^9+7相乘不超過(guò)longlong的特點(diǎn)，我們就能避免溢出。

　　相加則類似于b=2的情況。

　　以上。

原文鏈接：https://luospaces.com/posts/%e5%af%b91097%e5%8f%96%e6%a8%a1