Download presentation
Presentation is loading. Please wait.
1
10791: Minimum Sum LCM ★★★☆☆ 題組：Problem Set Archive with Online Judge
解題者：黃啟貿 解題日期：2018年4月19日 題意：任一正整數都可以表示為某一組正整數的LCM. 例如12可以表示 為1,12或12,12或3,4或4,6或1,2,3,4等的LCM. 一個正整數N, 找出一組至少兩個LCM為N的正整數. 可能會有無限種組 合, 此題必須選擇元素總和最小的組合, 並打印此組合元素的總和. 例 如N = 12, 應該打印3 + 4 = 7, 因為3和4的LCM是12並且7是可能組合 的最小總和. 1
2
解法：以 N 為 LCM 之數個正整數其 GCD 為 1 才會有最小總和,
題意範例： Sample Input Sample Output 12 Case 1: 7 10 Case 2: 7 5 Case 3: 6 解法：以 N 為 LCM 之數個正整數其 GCD 為 1 才會有最小總和, 因此正整數總和為最小之組合為每個質因數之最大次方(仍須為 N 之因數). 最小組合分為兩種情況: (1) N 僅有一個質因數(可能為 N 本身 或 N 的次方根) ---此情況之正整數組合即為 N 與 1, 因此總和為 N + 1. (2) N 有兩個以上的質因數 ---此情況之正整數組合總和為其所有質因數最大次方(仍須為 N 之因數)的總和. (註 1 : 判斷是否為質數只須從 1 找到 根號 N 仍不存在 1 以外的因數為止) (註 2 : 大於等於 根號 N 的質因數至多只有 1 個) 2
3
long long int func(int x){ int i, j, num, temp, sq;
解法範例： long long int func(int x){ int i, j, num, temp, sq; // num = x 的質因數個數, temp = x 的暫存值, sq = x 的平方根 long long int sum; // 所有質因數最大次方後之總和 int fac[MAX][2] = {}; // 存取每個質因數及其次方數 if(x == 1) // 若 x = 1, 則組合為 (1, 1) return (1 + 1); else if(prm(x)){ // prm: 回傳是否為質數 sum = x; // 若 x 為質數, 則質因數僅有 x 本身, 組合為 (1, x) return (sum + 1); } 3
4
else{ num = sum = 0, temp = x, sq = (int)(sqrt((double)x) + 0
else{ num = sum = 0, temp = x, sq = (int)(sqrt((double)x) + 0.5); // 變數初始化 for(i = 1; i <= sq; i++) // 找到根號 x 為止, 仍有所剩之數即為一次質因數 if(prm(i) && temp % i == 0){ // 判斷是否為質因數 for(j = 0; temp % i == 0; j++) // 找出質因數與其最大次方 temp /= i; fac[num][0] = i, fac[num][1] = j; // 記錄質因數與其最大次方 num++; // 質因數個數計數 + 1 if(temp <= 1) // 若已找完所有質因數則跳出迴圈 break; } if(temp > 1) // 大於根號 x 之僅剩一次質因數 fac[num][0] = temp, fac[num][1] = 1, num++; for(i = 0; i < num; i++) // 所有質因數最大次方後作總和 sum += (long long int)(pow((double)fac[i][0], fac[i][1]) + 0.5); if(num <= 1) // 只存在一個質因數(即 x 為其質因數作最大次方), 組合為(1, x) return (sum + 1); else // 存在多個質因數 return sum; 4
5
題意範例(增改)： 解法範例(增改)： (1) N 僅有一個質因數(可能為 N 本身 或 N 的次方根)
Sample Input: Sample Output: 12 7 (12 = 2 ^ 2 * 3 2 ^ = 7) 10 7 (10 = 2 * 5 = 7) 5 6 (5 = 5 = 6) 解法範例(增改)： (1) N 僅有一個質因數(可能為 N 本身 或 N 的次方根) N 本身 -- ex: 7 = 7 = 8 N 的次方根 -- ex: 9 = 3 ^ 2 3 ^ = 10 (2) N 有兩個以上的質因數 ex: 18 = 2 * 3 ^ 2 ^ 2 = 11 24 = 2 ^ 3 * 3 2 ^ = 11 36 = 2 ^ 2 * 3 ^ 2 2 ^ ^ 2 = 13 750 = 2 * 3 * 5 ^ 3 ^ 3 = 130 5
Similar presentations
