[MATH]INTEGERS

這條問題,真正,而且能在大部份情況下能用的答案是中國剩餘定理。

首先留意,7,8,9三個數是兩兩互質的。就是說(7,8)沒有公因數,(7,9)沒有公因數,(8,9)也沒有公因數。這種情況,我們可以找到

除7和8都能除盡,但除9餘1的數。這個數可以用7 x 8 = 56的倍數去找,最後找到是280.
留意280 / 7 = 40, 280 / 8 = 35, 280/9 = 31...1

除7和9都能除盡,但除8餘1的數。這個數可以用7 x 9 = 63的倍數去找,最後找到是441.
留意441 / 7 = 63, 441 / 9 = 49, 441/8 = 55...1

除8和9都能除盡,但除7餘1的數。這個數可以用8 x 9 = 72的倍數去找,最後找到是288.
留意288 / 8 = 36, 288 / 9 = 32, 288/7 = 41...1

(注：除了每個倍數試之外，其實也可以使用Extended Euclidean Algorithm去找這些數，這個方法會快很多，這裏不談了）

這些數非常有用,因為我們可以用乘法和加法隨意控制餘數。

比方說,我想要一個數除7餘2,除8除9都能除盡的話,這個數就是288 x 2 = 576
又例如,我想要一個數除7餘2,除8餘1,除9能除盡的話這個數就是288 x 2 + 441 x 1 = 1017

回應題目,要求除7餘4,除8餘5,除9餘6的,答案當然就是 280 x 6 + 441 x 5 + 288 x 4 = 5037

留意,這些數加減LCM都不會影響餘數的性質,所以5037 - 504 都是可以的, 5037 - 504 * 10都是可以的。
如果要找最少而又符合題目要求的正整數,它就是501, 因為 5037 / (7 x 8 x 9) = 9 ... 501

樓上用LCM的計法是正確的,而且比較簡單。如果這是一條小學生的題目,絕對應該用他的方法。但是他是方法一定要餘數剛剛好相差的數目好整齊(4,5,6) (7,8,9)。

如果不整齊,他的方法就行不通了。我的方法則是任何兩兩互質的數都可以使用。

有關Extended Euclidean Algorithm
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

有關中國剩餘定理
http://en.wikipedia.org/wiki/Chinese_remainder_theorem

2007-05-10 12:05:36 補充：
如果除7餘3的話，用我的方法,答案就是280 x 6 加 441 x 5 加 288 x 3 = 47494749 除 504 = 9 餘 213也能快速地找到213

2007-05-11 14:39:58 補充：
謝謝

good!

Dividing by 7 gives a remainder of 4 = 11.
Dividing by 8 gives a remainder of 5 = 13.
Dividing by 9 gives a remainder of 6 = 15.

計這條數...當然要用到chinese reminder theorem.

(8x9)y1 mod 7 = 1
y1=4
(7x9)y2 mod 8 = 1
y2=7
(7x8)y3 mod 9 = 1
y3=5

The least value = (72x4x4+63x7x5+56x5x6) mod 504 = 501

The LCM for 7, 8, 9 is 7 X 8 X 9 = 504, therefore the answer is 504 - (7 - 4) = 504 - (8 - 5) = 504 - (9 - 6) = 504 - 3 = 501

answer is 501

I found it with the help of ms excel

2007-05-10 10:33:18 補充：
雁妮 的答案好似好正確,但如果條問改為除7是會剩3不是剩4的話,佢個方法就會不成立但我卻知案案會變為213213/除7剩3213/除8剩5213/除9剩6