一、同余

    我們來了解一下什么是“同余”。簡單來說就是，如果兩個數(shù)都除以某個數(shù)能夠有相同的余數(shù)，那么我們就說這兩個數(shù)“同余”。不過這次我們用嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)概念來表述：

    兩個整數(shù) a，b，若它們除以整數(shù) m 所得的余數(shù)相等，則稱 a，b 對于模 m 同余

    記作

    讀作 a 同余于 b 模 m ，或讀作 a 與 b 關(guān)于模 m 同余。

    比如

    我們再來了解一下相關(guān)的性質(zhì)：

1. 如果 ，那么 m | (a − b) ，這里 m | (a − b) 表示 (a − b) 能被 m 整除
2. 如果 ，, 那么
3. 如果 ，, 那么，，，
4. 如果 ， 那么  

    有了這些性質(zhì)，判斷兩個數(shù)是否同余就可以用更簡單的方法了。根據(jù)性質(zhì)一，原來我們需要判斷 (a mod m) == (b mod m) 是否為真，現(xiàn)在就可以直接判斷 (a - b) mod m == 0 是否為真了。這樣就把其中一次求余運算變?yōu)闇p法運算了。一般來說減法要比除法更容易在計算機上實現(xiàn)，運算速度也更快。

二、求余 (a * b * c * d) mod m = ?

    由于計算機表示一個整數(shù)通常用 32bit 。而大量連乘運算則可能會導(dǎo)致整數(shù)溢出，這時我們就要利用求余一些性質(zhì)來進行處理了。把以上式子轉(zhuǎn)換為：

    已知： (a * b) mod m == ((a mod m) * b) mod m

    所以： (a * b * c * d) mod m = ((((((a mod m) * b) mod m) * c) mod m) * d) mod m

    這樣就把連乘運算分解了，每次可以先進行求余運算然后再進行乘法運算。