一、同余

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

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

    記作

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

    比如

    我們?cè)賮砹私庖幌孪嚓P(guān)的性質(zhì)：

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

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

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

    由于計(jì)算機(jī)表示一個(gè)整數(shù)通常用 32bit 。而大量連乘運(yùn)算則可能會(huì)導(dǎo)致整數(shù)溢出，這時(shí)我們就要利用求余一些性質(zhì)來進(jìn)行處理了。把以上式子轉(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

    這樣就把連乘運(yùn)算分解了，每次可以先進(jìn)行求余運(yùn)算然后再進(jìn)行乘法運(yùn)算。