[Java] UVa 1730 Sum of MSLCM

題目連結

題意:
maximum sum LCM(MSLCM): 找到一個集合，最小公倍數(LCM)為N且該集合的和為最大

舉例:
MSLCM(2) = 3:
LCM(1, 2) = 2 且 1+2=3為 最大的和

題目給定 N (1<N<20000001) (2千萬)
要求MSLCM(2) ~ MSLCM(N)的和

如: N = 10
LCM(1, 2) = 2, 1+2=3
LCM(1, 3) = 3, 1+3=4
LCM(1, 2, 4) = 4, 1+2+4=7
LCM(1, 5) = 5, 1+5=6
LCM(1, 2, 3, 6) = 6, 1+2+3+6=12
LCM(1, 7) = 7, 1+7=8
LCM(1, 2, 4, 8) = 8, 1+2+4+8=15
LCM(1, 3, 9) = 9, 1+3+9=13
LCM(1, 2, 5, 10) = 10, 1+2+5+10=18

Total = 3+4+7+6+12+8+15+13+18 = 86

解法:
觀察上述例子，會發現
集合的總和為最大，恰為 N 之所有因數形成的集合
但不太可能從 2 ~ N 一一找因數還加總

我們發現，也把MSLCM(1)算進去的話
從1~N(這裡N=10)的所有因數出現次數統計如下:
1:10次  2:5次  3:3次  4~5:2次  6~10:1次
次數恰為 (N/因數) 的值(小數無條件捨去，即程式語言的整數相除)

所以原本的題目可以這樣解:
從2~N依序代入上述關係求得並加總

本來以為這樣就節省很多時間了
但N可以到20000000，所以O(n)還是TLE了

我們進一步發現
這些因數從小到大，出現次數會遞減
而且連續因數的次數可能都一樣(像上述的4, 5都是2次，6~10都是1次)
所以我們希望，次數相同的因數一起算

此時用到類似binary search的做法
得到每個次數的起始與結束區間(左右區間)
把區間內的因數加總後，再乘上次數

以N = 10為例

每次先用前一次結果得到左區間，初始為0，先得到第2列的左=1
剛剛知道因數對應次數可以 (N/因數)得到，所以第2列的次數 t = 10/1
再來是右區間， N/t 即可

這要從因數6~10觀察
10/6~10/10都會得到次數1，發現除以次數: 10/1得到的10會在最右邊

左區間與右區間之間的因數要全部加起來，像6~10，就是6+7+...+10
可以用梯形公式 (6+10)*5/2 = 40 ，再 * 1 (次數) = 40

每個次數算完加總後，最後要扣掉MSLCM(1)的1，所以 87-1 = 86


很多題目可以線性時間做完
但若測資範圍極大，一定TLE，就要思考優化的解法了QQ

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext()) {
	long N = sc.nextLong();
	if (N == 0)
	break;
	long sum = 0;
	long ans = 0, times, R, L = 1;
	long count = 0;
	while (L <= N) {
	times = N / L;
	R = N / times;
	ans += times * ((L + R) * (R - L + 1) / 2);
	L = R + 1;
	count++;
	}
	System.out.println(ans - 1);
	}
	}
	}

view raw UVa1730.java hosted with ❤ by GitHub