POJ1006: 中國剩余定理的完美演繹

問題描述

     人自出生起就有體力，情感和智力三個(gè)生理周期，分別為23，28和33天。一個(gè)周期內(nèi)有一天為峰值，在這一天，人在對(duì)應(yīng)的方面（體力，情感或智力）表現(xiàn)最好。通常這三個(gè)周期的峰值不會(huì)是同一天。現(xiàn)在給出三個(gè)日期，分別對(duì)應(yīng)于體力，情感，智力出現(xiàn)峰值的日期。然后再給出一個(gè)起始日期，要求從這一天開始，算出最少再過多少天后三個(gè)峰值同時(shí)出現(xiàn)。

問題分析

      首先我們要知道，任意兩個(gè)峰值之間一定相距整數(shù)倍的周期。假設(shè)一年的第N天達(dá)到峰值，則下次達(dá)到峰值的時(shí)間為N+Tk(T是周期，k是任意正整數(shù))。所以，三個(gè)峰值同時(shí)出現(xiàn)的那一天(S)應(yīng)滿足

      S = N1 + T1*k1 = N2 + T2*k2 = N3 + T3*k3

N1,N2,N3分別為為體力，情感，智力出現(xiàn)峰值的日期， T1，T2,T3分別為體力，情感，智力周期。 我們需要求出k1,k2,k3三個(gè)非負(fù)整數(shù)使上面的等式成立。

     想直接求出k1,k2,k3貌似很難，但是我們的目的是求出S， 可以考慮從結(jié)果逆推。根據(jù)上面的等式，S滿足三個(gè)要求：除以T1余數(shù)為N1，除以T2余數(shù)為N2，除以T3余數(shù)為N3。這樣我們就把問題轉(zhuǎn)化為求一個(gè)最小數(shù)，該數(shù)除以T1余N1，除以T2余N2,除以T3余N3。這就是著名的中國剩余定理，我們的老祖宗在幾千年前已經(jīng)對(duì)這個(gè)問題想出了一個(gè)精妙的解法。依據(jù)此解法的算法，時(shí)間復(fù)雜度可達(dá)到O(1)。下面就介紹一下中國剩余定理。

中國剩余定理介紹

     在《孫子算經(jīng)》中有這樣一個(gè)問題：“今有物不知其數(shù)，三三數(shù)之剩二（除以3余2），五五數(shù)之剩三（除以5余3），七七數(shù)之剩二（除以7余2），問物幾何？”這個(gè)問題稱為“孫子問題”，該問題的一般解法國際上稱為“中國剩余定理”。具體解法分三步：

1. 找出三個(gè)數(shù)：從3和5的公倍數(shù)中找出被7除余1的最小數(shù)15，從3和7的公倍數(shù)中找出被5除余1 的最小數(shù)21，最后從5和7的公倍數(shù)中找出除3余1的最小數(shù)70。
2. 用15乘以2（2為最終結(jié)果除以7的余數(shù)），用21乘以3（3為最終結(jié)果除以5的余數(shù)），同理，用70乘以2（2為最終結(jié)果除以3的余數(shù)），然后把三個(gè)乘積相加（15*2+21*3+70*2）得到和233。
3. 用233除以3，5，7三個(gè)數(shù)的最小公倍數(shù)105，得到余數(shù)23，即233%105=23。這個(gè)余數(shù)23就是符合條件的最小數(shù)。

     就這么簡單。我們?cè)诟袊@神奇的同時(shí)不禁想知道古人是如何想到這個(gè)方法的，有什么基本的數(shù)學(xué)依據(jù)嗎？

中國剩余定理分析

     我們將“孫子問題”拆分成幾個(gè)簡單的小問題，從零開始，試圖揣測古人是如何推導(dǎo)出這個(gè)解法的。

     首先，我們假設(shè)n1是滿足除以3余2的一個(gè)數(shù)，比如2，5，8等等，也就是滿足3*k+2（k>=0）的一個(gè)任意數(shù)。同樣，我們假設(shè)n2是滿足除以5余3的一個(gè)數(shù)，n3是滿足除以7余2的一個(gè)數(shù)。

     有了前面的假設(shè)，我們先從n1這個(gè)角度出發(fā)，已知n1滿足除以3余2，能不能使得 n1+n2 的和仍然滿足除以3余2？進(jìn)而使得n1+n2+n3的和仍然滿足除以3余2？

     這就牽涉到一個(gè)最基本數(shù)學(xué)定理，如果有a%b=c,則有(a+kb)%b=c(k為非零整數(shù))，換句話說，如果一個(gè)除法運(yùn)算的余數(shù)為c，那么被除數(shù)與k倍的除數(shù)相加（或相減）的和（差）再與除數(shù)相除，余數(shù)不變。這個(gè)是很好證明的。

     以此定理為依據(jù)，如果n2是3的倍數(shù)，n1+n2就依然滿足除以3余2。同理，如果n3也是3的倍數(shù)，那么n1+n2+n3的和就滿足除以3余2。這是從n1的角度考慮的，再從n2，n3的角度出發(fā)，我們可推導(dǎo)出以下三點(diǎn)：

1. 為使n1+n2+n3的和滿足除以3余2，n2和n3必須是3的倍數(shù)。
2. 為使n1+n2+n3的和滿足除以5余3，n1和n3必須是5的倍數(shù)。
3. 為使n1+n2+n3的和滿足除以7余2，n1和n2必須是7的倍數(shù)。

    因此，為使n1+n2+n3的和作為“孫子問題”的一個(gè)最終解，需滿足：

1. n1除以3余2，且是5和7的公倍數(shù)。
2. n2除以5余3，且是3和7的公倍數(shù)。
3. n3除以7余2，且是3和5的公倍數(shù)。

    所以，孫子問題解法的本質(zhì)是從5和7的公倍數(shù)中找一個(gè)除以3余2的數(shù)n1，從3和7的公倍數(shù)中找一個(gè)除以5余3的數(shù)n2，從3和5的公倍數(shù)中找一個(gè)除以7余2的數(shù)n3，再將三個(gè)數(shù)相加得到解。在求n1，n2，n3時(shí)又用了一個(gè)小技巧，以n1為例，并非從5和7的公倍數(shù)中直接找一個(gè)除以3余2的數(shù)，而是先找一個(gè)除以3余1的數(shù)，再乘以2。

    這里又有一個(gè)數(shù)學(xué)公式，如果a%b=c，那么（a*k）%b=a%b+a%b+…+a%b=c+c+…+c=kc（k>0）,也就是說，如果一個(gè)除法的余數(shù)為c，那么被除數(shù)的k倍與除數(shù)相除的余數(shù)為kc。展開式中已證明。

    最后，我們還要清楚一點(diǎn)，n1+n2+n3只是問題的一個(gè)解，并不是最小的解。如何得到最小解？我們只需要從中最大限度的減掉掉3，5，7的公倍數(shù)105即可。道理就是前面講過的定理“如果a%b=c,則有(a-kb)%b=c”。所以（n1+n2+n3）%105就是最終的最小解。

總結(jié)

   經(jīng)過分析發(fā)現(xiàn)，中國剩余定理的孫子解法并沒有什么高深的技巧，就是以下兩個(gè)基本數(shù)學(xué)定理的靈活運(yùn)用：

1. 如果 a%b=c , 則有 (a+kb)%b=c (k為非零整數(shù))。
2. 如果 a%b=c，那么 (a*k)%b=kc (k為大于零的整數(shù))。