Problem Solving►UVa

UVa 1730 - Sum of MSLCM

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

Solution

1
2
3
4
5
6
7
8
F(n): {裡面元素的最小公倍數是 n}
F(1): {1}
F(2): {1, 2}
F(3): {1, 3}
F(4): {1, 2, 4}
F(5): {1, 5}
...
F(10): {1, 2, 5, 10}

去加總每個 MSLCM(i) 的 set 中出現的數字，像是 2 會在 F(2)、F(4)、F(6)、F(8)、F(10) 中出現(n = 10)。
依次去相加到 n 即可，記得減掉一開始的 1。
Ans: (1 + 2) + (1 + 3) + (1 + 2 + 4) + … + (1 + 2 + 5 + 10)

$\sum_{i=2}^n {MSLCM(i)} =$

$\sum_{i=1}^n{(i\times\lfloor{ \frac{n}{i} }\rfloor)} - 1$

(直接同一行打兩個 \sum 一直出錯是怎麼…)

而直接計算出每個數字的出現次數可以更快算出答案，例如 n = 10，2 的出現次數就是 $\lfloor{\frac{10}{2}}\rfloor = 5$，
3 的則是： $\lfloor{\frac{10}{3}}\rfloor = 3$。

最重要的是會有哪些數字出現次數會是一樣的，
$\lfloor{\frac{10}{6}}\rfloor = \lfloor{\frac{10}{7}}\rfloor = \lfloor{\frac{10}{8}}\rfloor = \lfloor{\frac{10}{9}}\rfloor =\lfloor{\frac{10}{10}}\rfloor = 1$

times * ((L + R) * (R - L + 1) / 2) => 5 * ((6 + 10) * (10 - 6 + 1) / 2)

用二分的方法去找，以 i = 1 ~ 10 來說各數字依序出現的次數是：10, 5, 3, 2, 2, 1, 1, 1, 1, 1。

Code

UVa 1730
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#define N 20000001
typedef long long LL;
int main()
{
    //SUM(MSLCM(n)) = [SUM(i*floor(n/i))]
    //i = 1 ~ n
    static LL ans[N] = {};
    for (int i = 2; i < N; ++i)
    {
        //處理在 MSLCM(j) 的 set 中出現的 i
        //j 為 i 的倍數
        for (int j = i; j < N; j += i)
            ans[j] += i;
        //MSLCM(n)
        ans[i] += ans[i - 1] + 1; //沒處理 1，要加上去
    }

    int n;
    while (scanf("%d", &n) && n)    
        printf("%lld\n", ans[n]);    

    return 0;
}

二分加速

UVa 1730
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>

inline int read()
{
    int n = 0;
    char c;
    while ((c = getchar()) >= '0' && c <= '9')
        n = n * 10 + c - '0';
    return n;
}
int main()
{
    int n;
    while ((n = read()) != 0)
    {
        //i = 1 ~ n
        long long ans = 0, times, R, L = 1;
        while (L <= n)
        {
            times = n / L;
            R = n / times;
            ans += times * ((L + R) * (R - L + 1) / 2);
            L = R + 1;
        }

        printf("%lld\n", ans - 1);
    }

    return 0;
}