[Java] UVa 10791 Minimum Sum LCM

題目連結

題意:
給定一個數 N
N 可以表示成至少 2 個數的最小公倍數 (LCM)
求那些數最小總和為多少?

如: N = 12
下列組合的 LCM都是 12
(1, 12), (3, 4), (12, 12), (1, 2, 3, 4), ...
其中最小總和為 3+4 = 7

解法:
先將 N 進行質因數分解
然後把相同質因數相乘得到某些數
也就是所有質因數的最高次 (仍是N的因數)

例如:
12 = 2*2*3 = 4*3 
360 = 2*2*2*3*3*5 = 8*9*5

可以觀察到， N 可以表示成這些數的乘積
他們不但彼此互質(符合 LCM 為 N 的特性)
總和也會最小

因此，只要質因數分解
當找到質因數，就持續分解得該質因數的最高次數
最後求這些數總和即可

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int t = 0;
	while (sc.hasNext()) {
	t++;
	long N = sc.nextLong();
	long sq = (long)Math.sqrt(N+0.5);
	long sum = 0;
	int count = 0;
	if (N == 0)
	break;
	if (N == 1)
	sum = 2;
	else {
	for (long i = 2; i <= sq; i++) {
	if (N % i == 0) { //prime factor
	long factor = 1;
	while (N % i == 0 && N > 1){
	factor *= i;
	N /= i;
	}
	sum += factor;
	count++;
	}
	}
	if (N > 1) { //prime
	count++;
	sum += N;
	}
	//number of prime factor = 1
	if (count == 1)
	sum++;
	}
	System.out.println("Case " + t + ": " + sum);
	}
	}
	}

view raw UVa10791.java hosted with ❤ by GitHub