1730: Sum of MSLCM ★★☆☆☆ 題組：Problem Set Archive with Online Judge

Presentation on theme: "1730: Sum of MSLCM ★★☆☆☆ 題組：Problem Set Archive with Online Judge"— Presentation transcript:

1 1730: Sum of MSLCM ★★☆☆☆ 題組：Problem Set Archive with Online Judge
解題者：陳冠智 解題日期：2018年6月7日 題意：對於一個數字N (1<N< )，maximum sum LCM(MSLCM)表示找到一個數字集合的最小公倍數為N，且該集合的和為最大。題目給定N，要求從2至N的MSLCM總和，即 𝑖=2 N 𝑀𝑆𝐿𝐶𝑀(𝑖) 。當N等於0時結束。

2 𝑖=2 4 𝑀𝑆𝐿𝐶𝑀(𝑖) = 𝑀𝑆𝐿𝐶𝑀(2) + 𝑀𝑆𝐿𝐶𝑀(3) + 𝑀𝑆𝐿𝐶𝑀(4) 𝑀𝑆𝐿𝐶𝑀(2) = 3:
題意範例： 最小公倍數的最大總和 – MSLCM 當 N = 4 𝑖=2 4 𝑀𝑆𝐿𝐶𝑀(𝑖) = 𝑀𝑆𝐿𝐶𝑀(2) + 𝑀𝑆𝐿𝐶𝑀(3) + 𝑀𝑆𝐿𝐶𝑀(4) 𝑀𝑆𝐿𝐶𝑀(2) = 3: LCM(1, 2) = 2 且 1+2=3為 Maximum Sum of set 𝑀𝑆𝐿𝐶𝑀(3) = 4: LCM(1, 3) = 3 且 1+3=4為 Maximum Sum of set 𝑀𝑆𝐿𝐶𝑀(4) = 7: LCM(1, 2, 4) = 4 且 1+2+4=7為 Maximum Sum of set 𝑖=2 4 𝑀𝑆𝐿𝐶𝑀(𝑖) = = 14 (Input) (Output)

3 𝑖=2 10 𝑀𝑆𝐿𝐶𝑀(𝑖) = 3+4+7+6+12+8+15+13+18=86
題意範例： 最小公倍數的最大總和 – MSLCM 當 N = 10 𝑖=2 10 𝑀𝑆𝐿𝐶𝑀(𝑖) = 𝑀𝑆𝐿𝐶𝑀(2)+𝑀𝑆𝐿𝐶𝑀(3)+ … +𝑀𝑆𝐿𝐶𝑀(10) (Input) 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, =12 LCM(1, 7) = 7, 1+7=8 LCM(1, 2, 4, 8) = 8, =15 LCM(1, 3, 9) = 9, 1+3+9=13 LCM(1, 2, 5, 10)=10, =18 𝑖=2 10 𝑀𝑆𝐿𝐶𝑀(𝑖) = =86 N MSLCM(N) 2 3 4 7 5 6 12 8 15 9 13 10 18

4 使集合的總和為最大  該集合為N之所有因數 原始題意: 給定N (1<N<20000001)，求2~N的所有因數總和
解法(1)： 使集合的總和為最大  該集合為N之所有因數 原始題意: 給定N (1<N< )，求2~N的所有因數總和 2: (1, 2) 3: (1, 3) 4: (1, 2, 4) 5: (1, 5) 6: (1, 2, 3, 6) 7: (1, 7) 8: (1, 2, 4, 8) 9: (1, 3, 9) 10: (1, 2, 5, 10) 1. 求出2~N的因數 2. 將這些數全部加總 #不太可能一個一個找因數

5 解法(2)： 觀察因數出現次數 (N=10) 1: (1) 2: (1, 2) 3: (1, 3) 4: (1, 2, 4)
因數(f) 次數(t) 次數關係(t=N/f) 1 10 =10/1 2 5 =10/2 3 =10/3 4 =10/4 =10/5 6 =10/6 7 =10/7 8 =10/8 9 =10/9 =10/10 1: (1) 2: (1, 2) 3: (1, 3) 4: (1, 2, 4) 5: (1, 5) 6: (1, 2, 3, 6) 7: (1, 7) 8: (1, 2, 4, 8) 9: (1, 3, 9) 10: (1, 2, 5, 10)

6 解法(2)： 對於N，依 1~N 次數關係計算最終答案 以10為例: 總和 = 1 * (10/1) + 2 * (10/2)
因數(f) 次數(t) 1 10 2 5 3 4 6 7 8 9 總和 = 1 * (10/1) + 2 * (10/2) + 3 * (10/3) + 4 * (10/4) + … + 9 * (10/9) + 10 * (10/10) -1 = = 86 #題目問從2 ~ N之和  最後要扣掉N=1的結果: 1 #每筆N可達 2∗ 10 7 ，需要O(N)，還是會TLE

7 觀察: 出現次數會遞減，而且連續因數的次數可能都一樣 目標: 次數相同的因數一起算
解法(3)： 觀察: 出現次數會遞減，而且連續因數的次數可能都一樣 目標: 次數相同的因數一起算 因數(f) 次數(t) 1 10 2 5 3 4 6 7 8 9 𝑙, r = 0 每次 { 𝑙 = r+1 計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) } (因數的左, 右區間) (第一次因數左區間從1開始) (左區間~右區間) #右區間: ∵ 10/6 = 10/7 = 10/8 = 10/9 = 10/10 =1 (in code) ∴當10/1, 可以得到最大的因數10

8 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 1 𝑙 = r+1
計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 1

9 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 𝑙 = r+1
計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1

10 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 𝑙 = r+1
計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1

11 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 2 𝑙 = r+1
計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 2

12 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 5 2 𝑙 = r+1
計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 5 2

13 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 5 2 20 𝑙 = r+1
計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 5 2 20

14 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 5 2 20 3 9 29
計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 5 2 20 3 9 29

15 解法範例： 以N=10為例: 總和 = 2 * [(4+5) * 2 / 2] = 18 出現次數(t) 因數左區間(𝑙) 因數右區間(r)
計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 5 2 20 3 9 29 4 18 47 梯形公式 總和 = 2 * [(4+5) * 2 / 2] = 18

16 解法範例： 以N=10為例: 最後結果: 87 – 1 = 86 (扣掉N=1的情況)
𝑙 = r+1 計算因數1的次數t = N/𝑙 計算相同次數的因數右區間r = N/t 加總: 所有因數 [𝑙+(𝑙+1)+…+r] * 次數(t) 解法範例： 以N=10為例: 最後結果: 87 – 1 = 86 (扣掉N=1的情況) 出現次數(t) 因數左區間(𝑙) 因數右區間(r) 總和 累積總和 10 1 5 2 20 3 9 29 4 18 47 6 40 87 梯形公式 總和 = 1 * [(6+10) * 5 / 2] = 40

17 討論： 題目遇到N=0才停止，假設有 r 筆測資 解法(2)計算1~N個別因數個數  O rN 解法(3)以次數為單位
 O r log N 因數(f) 次數(t) 1 10 2 5 3 4 6 7 8 9 N= 時，有8943個不同次數