POJ 1006 Biorhythms

POJ 1003，1004，1005 比較簡單，很快就解決了。有個小插曲，剛開始做ACM不太懂，最近提交問題反饋最多的就是Runtime Error，開始我以為是超時，1方面我懷疑是否是Java跑得太慢了，然后去了解發現有些國際大賽推薦用java，那說明java本身是不慢的。另外一方面我懷疑是我程序太爛，每次都很耗時，所以每次遇到Runtime Error問題就去優化代碼，但有時候怎樣優化都不行。在做POJ1005的時候，網上的代碼貼上去AC了，但是我的不行，但兩個程序已完全1樣了，這個時候才發現罪魁罪魁是我提交時總是帶著包名（有時候手動是去了的）。

POJ 1006這個題目我雖然能提交通過，但我的方法更多的算暴力破解。

解題的關鍵是從復雜錯亂的描寫中抽象出問題的本質，也就是將現象轉化為數學問題。POJ1006這個問題的難點是背后的數學問題――中國剩余定理。

1個數除3余2，除5余3，除7余2。可以用初等數論中的同余方程組來求解，利用同余的符號，可以將上述問題轉化為下面的同余方程組：
x ≡ 2 (mod 3)；
x ≡ 3 (mod 5)；
x ≡ 2 (mod 7)；
不難看出上述同余方程組的解其實不唯1，由于如果x是1個解，則x+3*5*7*k=x+105k也是該同余方程組的1個解。事實上，從3，5，7兩兩互質可知上述同余方程組的任意兩個解相差105的倍數。如何求出上述同余方程組最小的那個解呢？我們的先人聰明的把問題轉化為以下3個非常特殊的同余方程組的求解
a ≡ 1 (mod 3)； b ≡ 0 (mod 3)； c ≡ 0 (mod 3)；
a ≡ 0 (mod 5)； b ≡ 1 (mod 5)； c ≡ 0 (mod 5)；
a ≡ 0 (mod 7)； b ≡ 0 (mod 7)； c ≡ 1 (mod 7)；
則2a+3b+2c就是原同余方程組的1個解（即2a+3b+2c是被3除余a，被5除余b，被7除余c的數），如果這個數小于105，則即為所求的最小整數解。經過簡單計算可知a可以取70，b可以取21，c可以取15。計算可得2a+3b+2c=233，除以105后的余數23就是所求的最小正整數解。

回到POJ1006這個題目，已知number % 23 = p，number % 28 = e，number % 33 = i
使33*28*a被23除余1，可得5544  ＝ 33*28*6
使23*33*b被23除余1，可得14421 ＝ 23*33*19
使23*28*c被33除余1，可得1288  ＝ 23*28*2
因此有（5544*p ＋ 14421*e ＋ 1288*i） % lcm(23, 28, 33) = number
又由于23，28，33互質，所以lcm(23, 28, 33) ＝ 21252。所以number ＝ (5544*p + 14421*e + 1288*i) % 21252，所求的是number-d，本題求的是最小整數解，避免n為負數需要在number-d<=0的時候加21252。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈