Least Common Multiple

Least Common Multiple

Problem Description
A least common multiple of three positive integers a、b、and c is the smallest positive integer m which is a multiple of a、b、and c. Given a positive integer n、find three positive integers a、b、and c such that n = a + b + c and the least common multiple of a、b、and c is minimized.

Input Format
Input data contains a set of positive numbers. Assume that all the numbers are no more than 10000. The last data is followed by 0、indicating the end of input data.

Output Format
For each positive integer n in the input file、print three positive integers a、b、and c、a <= b <= c、such that the least common multiple of a、b、and c is as small as possible.

Sample Input
35
100
9999
0

Sample Output
35=7+14+14
100=20+40+40
9999=3333+3333+3333

困難度：**

解題原理：
1. 以整數讀入正數 n 後進行處理，一次處理一個整數
2. 若為質數，a、b、c 三數必為 1+(n-1/2)+(n-1/2) 方能使 LCM 最小（此步驟亦可忽略）
3. 窮舉所有從 1 到 n/2 數進行 LCM 比較
4. 改進窮舉演算法：
b 可改寫為 p * a，p 為常數
c 可改鳥為 q * b，q 為常數
故當 a + p*a + q*b 時，LCM 必最小

延伸思考：
當 a、b、c 三數為 p、px、py 形式時，LCM 必為最小；令三數質因數為集合 S，x、y 為最小質因數 n 之 (n-1)/2，p 為 S - n，故 a+b+c = p+n+n

證明論點：
1. 證 a、b、c 三數改寫為 pa'、pa'b'、pa'b'c' 時，pa' pa'b'c'， pa'b' pa'b'c'
2. 證 pab = pabc
3. 證 p 必為最小質因數，LCM 方為最小
提示：(a+b)/2 >= (ab)^(0.5)

程式下載

原碼下載

參考來源：中山大學 九十二學年度電腦程式設計競賽 試題 Problem 2