Problem Solving►UVa

UVa 10791 - Minimum Sum LCM

Contents

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

Problem

題目網址
中文網址

給你某集合的最小公倍數，要你算出這個集合各元素相加的值，取總和最小的，集合內 至少 兩個元素。

Solution

用篩法建出質數表 prime[ ] 後，來做質因數分解:

  • $n$ 是 質數
    答案為 $1+n$
  • $n$ 是 合成數
    質因數分解後互質的各項相加，因為: $$\begin{aligned} &lcm(a,b) = {a \times b\over gcd(a,b)}\\\\ &gcd(a,b) = 1\\\\ &lcm(a,b) = a \times b \end{aligned}$$ 如果 $a$ 和 $b$ 都大於$1$的話，$a \times b > a + b$ ，所以相加比都乘在一起小。

$INT\_MAX = 2^{31}-1$
只需要找 $sqrt(INT\_MAX)$ (以下簡稱 $sqrt$ ) 以內的質數，原因是:

  • 小於 $sqrt$ 的自然在 prime[ ] 會處理到
  • 大於等於 $sqrt$
    • 是質數，答案為 $1+n$
    • 是合成數，必定有小於 $sqrt$ 的質因數，除掉後，剩餘的即是大於 $sqrt$ 的質因數。
      如果剩餘的為合成數，代表它可以被質因數分解，裡面的各項質數會大於 $sqrt$ ，而此合成數必定大於$sqrt \times sqrt$ ，這樣就超出題目給定的範圍了。

$2^{31}-1 = 2147483647$ 為質數，加 $1$ 後會有 overflow 的問題，獨立出來處理。
$1$ 不是質數或合成數。

Code

UVa 10791UVa 10791 - Minimum Sum LCM
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include<cstdio>
#define INT_MAX 2147483647
#define N 46340 //sqrt(INT_MAX)

int prime[N];
bool notPrime[N] = { true, true };
int getPrime();
int main()
{
    int Case = 0, n, p;
    p = getPrime();

    while (scanf("%d", &n) != EOF&&n)
    {
        Case++;

        if (n == INT_MAX)//2147483647 is prime
            printf("Case %d: 2147483648\n", Case);//2147483647 + 1
        else if (n == 1)
            printf("Case %d: 2\n", Case);
        else
        {
            int sum = 0, m = n;
          
            for (int i = 0; i < p&&prime[i] <= n; i++)
            {
                //質因數分解
                int count = 1;
                while (!(n%prime[i]))
                {
                    count *= prime[i];
                    n /= prime[i];
                }

                //相加各項
                if (count != 1)
                    sum += count;
            }

            if (sum == m)//本身就是質數，和為 1 + n
                sum++;
            else if (n != 1)//剩下的質數
                sum += n;

            printf("Case %d: %d\n", Case, sum);
        }
    }
    return 0;
}
int getPrime()
{
    int count = 0;
    for (int i = 2; i < N; i++)
        if (!notPrime[i])
        {
        prime[count++] = i;
        for (int j = i << 1; j < N; j += i)
            notPrime[j] = true;
        }

    return count;
}