由 中國餘數定理 到 PKU 1006 Biorhythms

PKU 1006 Biorhythms
http://acm.pku.edu.cn/JudgeOnline/problem?id=1006

題意是，給定 n 除以 23,28,33 的餘數及 d，現在要求 n-d 的最小值。

----------------------------------------------------------

說起中國餘數定理，就必定會想起"韓信點兵"。

用日常生活例子來說，你不知你朋友的年紀 y ，但問他 (y mod 3) --> r3, (y mod 5) --> r5 及 (y mod 7) --> r7 三個數可以輕易快速地計算 y。

y = (r3*70+r5*21+r7*15) mod 105

For example, 你朋友年紀 29 , r3 = 2, r5 = 4 , r7 = 1,

(r3*70+r5*21+r7*15) mod (3*5*7) = (140+84+15) mod 105 = 29。

原理是 :
70 除以 3 餘 1 ，並是其他兩數的倍數 ;
21 除以 5 餘 1 ，並是其他兩數的倍數 ;
15 除以 7 餘 1 ，並是其他兩數的倍數 ;

因此 15 無論加多少次都不會影響除以 3 及 5 的餘數。
而把 15 乘以 r7 便可以控制到除以 7 的餘數。
如此類推......

不妨稱 70 是 3 的"好數"，21 是 5 的"好數"，15 是 7 的"好數"。

現在問題是如何找出給定除數的"好數"。

例如新的一個系統給定除數 5,11,13,17， (除數最好要互質，否則有機會出現茅盾，如除4餘1，同時除2除0)

又給出 y,r5,r11,r13,r17，如何求 y 呢?

問題即是如何找出 r5,r11,r13,r17，

利用上述原理寫個程序，

for (i=1;i<5;++i) 5="=" y="(r5*2431+r11*9945+13*11220+17*715)" style="font-weight: bold;">一般化後的式子為，除數是 x1,x2,....xn，兩兩互質。

y = sum(rxi*xi的好數) mod product(xi) , for 1<= i <=n
--------------------------------------------

回到 PKU 1006，解決方法是找出 23,28,33 的"好數"，然後一條式子......

用以上方法代替暴力法，時間複雜度即可由 O(21252) 降至 O(1)。

輕鬆解決。

--------------------------------------------
題外話 :

若果這題的除數也是變量的話，則把預先計好的 rx1,rx2 .... rxn 的過程包含在程序中。

用這個方法代替暴力法，時間複雜度由 O(rx1 * rx2 * ... * rxn) 降至 O(rx1 + rx2 + ... rxn)。