模運算總結

模運算即求餘運算。“模”是“Mod”的音譯，模運算多應用于程式編寫中。 Mod的含義為求餘。模運算在數論和程式設計中都有着廣泛的應用，從奇偶數的判别到素數的判别，從模幂運算到最大公約數的求法，從孫子問題到凱撒密碼問題，無不充斥着模運算的身影。

　　例如11 Mod 2，值為1

　　上述模運算多用于程式編寫，舉一例來說明模運算的原理：

　　Turbo Pascal對mod的解釋是這樣的：

　　A Mod B=A-(A div B) * B （div含義為整除）

基本理論

　　基本概念：

　　給定一個正整數p，任意一個整數n，一定存在等式 n = kp + r ；

　　其中k、r是整數，且 0 ≤ r < p，稱呼k為n除以p的商，r為n除以p的餘數。

　　對于正整數p和整數a,b，定義如下運算：

　　取模運算：a % p（或a mod p），表示a除以p的餘數。

　　模p加法：(a + b) % p ，其結果是a+b算術和除以p的餘數，也就是說，(a+b) = kp +r，則(a + b) % p = r。

　　模p減法：(a-b) % p ，其結果是a-b算術差除以p的餘數。

　　模p乘法：(a * b) % p，其結果是 a * b算術乘法除以p的餘數。

　　說明：

　　1. 同餘式：正整數a，b對p取模，它們的餘數相同，記做 a ≡ b % p或者a ≡ b (mod p)。

　　2. n % p得到結果的正負由被除數n決定,與p無關。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。

基本性質

　　（1）若p|(a-b)，則a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)

　　（2）(a % p)=(b % p)意味a≡b (% p)

　　（3）對稱性：a≡b (% p)等價于b≡a (% p)

　　（4）傳遞性：若a≡b (% p)且b≡c (% p) ，則a≡c (% p)

運算規則

　　模運算與基本四則運算有些相似，但是除法例外。其規則如下：

　　(a + b) % p = (a % p + b % p) % p （1）

　　(a - b) % p = (a % p - b % p) % p （2）

　　(a * b) % p = (a % p * b % p) % p （3）

　　(a^b) % p = ((a % p)^b) % p （4）

　　結合率： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5）

　　((a*b) % p * c)% p = (a * (b*c) % p) % p （6）

　　交換率： (a + b) % p = (b+a) % p （7）

　　(a * b) % p = (b * a) % p （8）

　　配置設定率： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）

　　重要定理：若a≡b (% p)，則對于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）

　　若a≡b (% p)，則對于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）

　　若a≡b (% p)，c≡d (% p)，則 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，

　　(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）

　　若a≡b (% p)，則對于任意的c，都有ac≡ bc (%p)； （13）

基本應用

　　1.判别奇偶數

　　奇偶數的判别是模運算最基本的應用，也非常簡單。易知一個整數n對2取模，如果餘數為0，則表示n為偶數，否則n為奇數。

　　2.判别素數

　　一個數，如果隻有1和它本身兩個因數，這樣的數叫做質數（或素數）。例如 2，3，5，7 是質數，而 4，6，8，9 則不是，後者稱為合成數或合數。

　　判斷某個自然數是否是素數最常用的方法就是試除法：用比該自然數的平方根小的正整數去除這個自然數，若該自然數能被整除，則說明其非素數。

　　C++實作功能函數：

[cpp] view plain copy print ?

1. 　bool IsPrime(unsigned int n)   
2. 　{   
3. 　unsigned maxFactor = sqrt(n); //n的最大因子   
4. 　for (unsigned int i=2; i<=maxFactor; i++)   
5. 　{   
6. 　if (n % i == 0) //n能被i整除，則說明n非素數   
7. 　{   
8. 　return false;   
9. 　}   
10. 　}   
11. 　return true;   
12. 　}   

　3. 最大公約數

　　求最大公約數最常見的方法是歐幾裡德算法（又稱輾轉相除法），其計算原理依賴于定理：gcd(a,b) = gcd(b,a mod b)

　　證明：a可以表示成a = kb + r，則r = a mod b

　　假設d是a,b的一個公約數，則有d|a, d|b，而r = a - kb，是以d|r

　　是以d是(b,a mod b)的公約數

　　假設d 是(b,a mod b)的公約數，則d | b , d |r ，但是a = kb +r

　　是以d也是(a,b)的公約數

　　是以(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。

　　C++實作功能函數：

[cpp] view plain copy print ?

1. 　　unsigned int Gcd(unsigned int a, unsigned int b)   
2. 　　{   
3. 　　if (b == 0)   
4. 　　return a;   
5. 　　return Gcd(b, a % b);   
6. 　　}   
7. 　　   
8. 　　unsigned int Gcd(unsigned int a, unsigned int b)   
9. 　　{   
10. 　　unsigned int temp;   
11. 　　while (b != 0)   
12. 　　{   
13. 　　temp = a % b;   
14. 　　a = b;   
15. 　　b = temp;   
16. 　　}   
17. 　　return a;   
18. 　　}   

4．模幂運算

　　利用模運算的運算規則，我們可以使某些計算得到簡化。例如，我們想知道3333^5555的末位是什麼。很明顯不可能直接把3333^5555的結果計算出來，那樣太大了。但我們想要确定的是3333^5555（%10），是以問題就簡化了。

　　根據運算規則（4）a^b% p = ((a % p)^b) % p ，我們知道3333^5555（%10）= 3^5555（%10）。由于3^4 = 81，是以3^4（%10）= 1。

　　根據運算規則（3） (a * b) % p = (a % p * b % p) % p ，由于5555 = 4 * 1388 + 3，我們得到3^5555（%10）=（3^(4*1388) * 3^3）（%10）=（（3^(4*1388)（%10）* 3^3（%10））（%10）

　　=（1 * 7）（%10）= 7。

　　計算完畢。

　　利用這些規則我們可以有效地計算X^N(% P)。簡單的算法是将result初始化為1，然後重複将result乘以X，每次乘法之後應用%運算符（這樣使得result的值變小，以免溢出），執行N次相乘後，result就是我們要找的答案。

　　這樣對于較小的N值來說，實作是合理的，但是當N的值很大時，需要計算很長時間，是不切實際的。下面的結論可以得到一種更好的算法。

　　如果N是偶數，那麼X^N =（X*X）^[N/2]；

　　如果N是奇數，那麼X^N = X*X^(N-1) = X *（X*X）^[N/2]；

　　其中[N]是指小于或等于N的最大整數。

　　C++實作功能函數：

[cpp] view plain copy print ?

1. 　unsigned int PowerMod(unsigned int x, unsigned int n, unsigned int p)   
2. 　{   
3. 　if (n == 0)   
4. 　{   
5. 　return 1;   
6. 　}   
7. 　unsigned int temp = PowerMod((x * x)%p, n/2, p); //遞歸計算（X*X）^[N/2]   
8. 　if ((n & 1) != 0) //判斷n的奇偶性   
9. 　{   
10. 　temp = (temp * x) % p;   
11. 　}   
12. 　return temp;   
13. 　}   

5.《孫子問題(中國剩餘定理)》

　　在我國古代算書《孫子算經》中有這樣一個問題：

　　“今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？”意思是，“一個數除以3餘2，除以5餘3，除以7餘2.求适合這個條件的最小數。”

　　這個問題稱為“孫子問題”.關于孫子問題的一般解法，國際上稱為“中國剩餘定理”.

　　我國古代學者早就研究過這個問題。例如我國明朝數學家程大位在他著的《算法統宗》（1593年）中就用四句很通俗的口訣暗示了此題的解法：

　　三人同行七十稀，五樹梅花甘一枝，七子團圓正半月，除百零五便得知。

　　"正半月"暗指15。"除百零五"的原意是，當所得的數比105大時，就105、105地往下減，使之小于105；這相當于用105去除，求出餘數。

　　這四句口訣暗示的意思是：當除數分别是3、5、7時，用70乘以用3除的餘數，用21乘以用5除的餘數，用15乘以用7除的餘數，然後把這三個乘積相加。加得的結果如果比105大，就除以105，所得的餘數就是滿足題目要求的最小正整數解。

　　根據剩餘定理，我把此種解法推廣到有n(n為自然數）個除數對應n個餘數，求最小被除數的情況。輸入n個除數（除數不能互相整除）和對應的餘數，計算機将輸出最小被除數。

　　C++實作功能函數： 　

[cpp] view plain copy print ?

1. 　unsigned int ResidueTheorem(const unsigned int devisor[], const unsigned int remainder[], int length)   
2. 　{   
3. 　unsigned int product = 1; //所有除數之乘積   
4. 　for (int i=0; i<length; i++)//計算所有除數之乘積   
5. 　{   
6. 　product *= devisor[i];   
7. 　}   
8. 　//公倍數數組，表示除該元素（除數）之外其他除數的公倍數   
9. 　unsigned int *commonMultiple = new unsigned int(length);   
10. 　for (int i=0; i<length; i++)//計算除該元素（除數）之外其他除數的公倍數   
11. 　{   
12. 　commonMultiple[i] = product / devisor[i];   
13. 　}   
14. 　unsigned int dividend = 0; //被除數，就是函數要傳回的值   
15. 　for (int i=0; i<length; i++)//計算被除數，但此時得到的不是最小被除數   
16. 　{   
17. 　unsigned int tempMul = commonMultiple[i];   
18. 　//按照剩餘理論計算合适的公倍數，使得tempMul % devisor[i] == 1   
19. 　while (tempMul % devisor[i] != 1)   
20. 　{   
21. 　tempMul += commonMultiple[i];   
22. 　}   
23. 　dividend += tempMul * remainder[i]; //用本除數得到的餘數乘以其他除數的公倍數   
24. 　}   
25. 　delete []commonMultiple;   
26. 　return (dividend % product); //傳回最小被除數   
27. 　}   

6. 凱撒密碼

　　凱撒密碼（caeser）是羅馬擴張時期朱利斯o凱撒（Julius Caesar）創造的，用于加密通過信使傳遞的作戰指令。

　　它将字母表中的字母移動一定位置而實作加密。注意26個字母循環使用，z的後面可以看成是a。

　　例如，當密匙為k = 3，即向後移動3位時，若明文為”How are you!”，則密文為”Krz duh btx!”。

　　凱撒密碼的加密算法極其簡單。其加密過程如下：

　　在這裡，我們做此約定：明文記為m，密文記為c，加密變換記為E(key1,m)（其中key1為密鑰），

　　解密變換記為D(key2,m)（key2為解密密鑰）（在這裡key1=key2,不妨記為key）。

　　凱撒密碼的加密過程可記為如下一個變換：c≡m+key (mod n） （其中n為基本字元個數）

　　同樣，解密過程可表示為：m≡c+key (mod n） （其中n為基本字元個數）

　　C++實作功能函數： 　　

[cpp] view plain copy print ?

1. 　　void Encrypt(const char proclaimedInWriting[], char cryptograph[], int key)   
2. 　　{   
3. 　　const int NUM = 26; //字母個數   
4. 　　int len = strlen(proclaimedInWriting);   
5. 　　for (int i=0; i<len; i++)   
6. 　　{   
7. 　　if (proclaimedInWriting[i] >= 'a' && proclaimedInWriting[i] <= 'z')   
8. 　　{//明碼是大寫字母，則密碼也為大寫字母   
9. 　　cryptograph[i] = (proclaimedInWriting[i] - 'a' + key) % NUM + 'a';   
10. 　　}   
11. 　　else if (proclaimedInWriting[i] >= 'A' && proclaimedInWriting[i] <= 'Z')   
12. 　　{//明碼是小寫字母，則密碼也為小寫字母   
13. 　　cryptograph[i] = (proclaimedInWriting[i] - 'A' + key) % NUM + 'A';   
14. 　　}   
15. 　　else   
16. 　　{//明碼不是字母，則密碼與明碼相同   
17. 　　cryptograph[i] = proclaimedInWriting[i];   
18. 　　}   
19. 　　}   
20. 　　cryptograph[len] = '\0';   
21. 　　}   
22. 　　   
23. 　　void Decode(const char cryptograph[], char proclaimedInWriting[], int key)   
24. 　　{   
25. 　　const int NUM = 26; //字母個數   
26. 　　int len = strlen(cryptograph);   
27. 　　for (int i=0; i<len; i++)   
28. 　　{   
29. 　　if (cryptograph[i] >= 'a' && cryptograph[i] <= 'z')   
30. 　　{//密碼是大寫字母，則明碼也為大寫字母，為防止出現負數，轉換時要加個NUM   
31. 　　proclaimedInWriting[i] = (cryptograph[i] - 'a' - key + NUM) % NUM + 'a';   
32. 　　}   
33. 　　else if (cryptograph[i] >= 'A' && cryptograph[i] <= 'Z')   
34. 　　{//密碼是小寫字母，則明碼也為小寫字母   
35. 　　proclaimedInWriting[i] = (cryptograph[i] - 'A' - key + NUM) % NUM + 'A';   
36. 　　}   
37. 　　else   
38. 　　{//密碼不是字母，則明碼與明密相同   
39. 　　proclaimedInWriting[i] = cryptograph[i];   
40. 　　}   
41. 　　}   
42. 　　proclaimedInWriting[len] = '\0';   
43. 　　}