Minimum Sum LCM UVA - 10791(唯一分解定理+筛素法)

cdplay 2018-08-10 原文

　　这道题用到了唯一分解定理，例如，我们将12通过唯一分解定理分解，得到2的平方*3，2的平方换成4，这样3加4就等于了7.

　　所以这道题的解题关键就是将输入值通过唯一分解定理分解，然后相加即可。

　　不过有特例，输入是1时，答案为1+1=2；以及输入是质数时(即只有一种因子)需要加一

　　另外看清本题的数据大小，不要溢出

不打表版：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 
 5 typedef unsigned long long ull;
 6 
 7 
 8 using namespace std;
 9 
10 ull lcm(ull a);
11 
12 int main()
13 {
14 
15     ios::sync_with_stdio(false);
16     cin.tie(0);
17     cout.tie(0);
18 
19     ull num;
20     int times = 1;
21 
22     while (cin >> num)
23     {
24         if (num == 0)
25             break;
26         ull end = lcm(num);
27         cout << "Case "<<times++<<": "<< end << endl;
28     }
29 
30     return 0;
31 }
32 
33 ull lcm(ull a)
34 {
35     if (a == 1)
36         return 2;
37 
38     ull m = (ull)sqrt(a+0.5);
39     int j = 0;
40     ull sum = 0;
41 
42     for (ull i = 2; i <= m; i++)
43     {
44         if (a%i == 0)
45         {
46             ull k=1;
47 
48             while (a%i == 0)
49             {
50                 k *= i;
51                 a /= i;
52             }
53             j++;
54             sum += k;
55 
56         }
57     }
58 
59     if (a > 1 || j == 0)
60     {
61         sum += a;
62         j++;
63     }
64 
65     if (j == 1)
66         sum++;
67 
68     return sum;
69 
70 
71 }

打素数表版：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 
 5 typedef unsigned long long ull;
 6 const int maxn =46340+20;//2的31次方-1加0.5开平方，然后加20
 7 int primes[maxn];
 8 bool p[maxn];
 9 int tol = 0;
10 
11 using namespace std;
12 
13 ull lcm(ull a);
14 void find_primes(ull n);
15 
16 int main()
17 {
18 
19     ios::sync_with_stdio(false);
20     cin.tie(0);
21     cout.tie(0);
22 
23     ull num;
24     int times = 1;
25     find_primes(maxn);
26 
27     while (cin >> num)
28     {
29         if (num == 0)
30             break;
31         ull end = lcm(num);
32         cout << "Case "<<times++<<": "<< end << endl;
33     }
34 
35     return 0;
36 }
37 
38 ull lcm(ull a)
39 {
40     if (a == 1)
41         return 2;
42 
43     ull m = (ull)sqrt(a+0.5);
44     int j = 0;
45     int t = 0;
46     ull sum = 0;
47 
48     for (ull i = primes[t]; i <= m; i=primes[++t])
49     {
50         if (a%i == 0)
51         {
52             ull k=1;
53 
54             while (a%i == 0)
55             {
56                 k *= i;
57                 a /= i;
58             }
59             j++;
60             sum += k;
61 
62         }
63     }
64 
65     if (a > 1 || j == 0)
66     {
67         sum += a;
68         j++;
69     }
70 
71     if (j == 1)
72         sum++;
73 
74     return sum;
75 
76 
77 }
78 
79 void find_primes(ull n)
80 {
81     memset(p, false, sizeof(p));
82 
83     for (int i = 2; i <= n; i++)
84     {
85         if (!p[i])
86         {
87             primes[tol++] = i;
88             for (int j = i * i; j <= n; j += i)
89                 p[j] = true;
90         }
91     }
92 }