UVA10791-Minimum Sum LCM(唯一分解定理基本应用)

基本思路：1、借助唯一分解定理分解数据。2、求和输出

知识点：1、筛法得素数 2、唯一分解定理模板代码 3、数论分析-唯一分解定理的性质

唯一分解定理：该定理通过素数将任意一个大于2的n分解为最小质数因子的幂的乘积。这是一个数字简化的过程。

题目易错点在于要求得到的是 ‘n的多个因子的和’，且该多个因子的最小公倍数为n。是多个，而不是两个！！由此看来，其实如果把分解定理得到的每一个‘质数^指数’的形式看作一个整数元素，那么，由n所得到的所有元素的最小公倍数恰好是n，因为每个元素的底数是素数。所以，‘最小的和’应当是‘所有整数元素的和’。

代码如下：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long LL;
 8 const int maxn = 100000;
 9 int prime[maxn];
10 int dn[1000],zn[1000];
11 LL psd[1000];
12 int num=1;
13 
14 int pre()//筛法出素数
15 {
16     memset(prime,0,sizeof(prime));
17     prime[0]=prime[1]=1;
18     for(int i=2;i<sqrt(maxn);i++)
19     {
20         if(prime[i])continue;
21         for(int j=2*i;j<maxn;j+=i)prime[j]=1;
22     }
23     return 0;
24 }
25 
26 int decomposition(int n)
27 {
28     memset(dn,0,sizeof(dn));
29     memset(zn,0,sizeof(zn));
30     int cur=0;
31     //
32     if(n==1)return 1;
33     for(int k=2;k<maxn;k++)
34     {
35         bool ok=false;
36         if(prime[k]==1)continue;//不是素数就不作为因子
37         while(n%k==0)
38         {
39             n/=k;
40             dn[cur]=k;
41             zn[cur]++;
42             ok=true;
43         }
44         if(ok)cur++;//cur表示到目前为止的因子个数
45         if(n==1)break;
46     }
47     if(n!=1){dn[cur]=n;zn[cur++]=1;}//最终n会变成1或者一个大质数
48     return cur;//返回因子的总个数
49 }
50 
51 LL change(int lenth)
52 {
53     LL m=0;
54     for(int i=0;i<lenth;i++)
55         m+=pow(dn[i],zn[i]);
56     return m;
57 }
58 
59 int solve(int n)
60 {
61     int lenth=decomposition(n);
62     printf("Case %d: ",num++);
63     if(lenth==1)
64     {
65         printf("%lld
",n+1);
66         return 0;
67     }
68     printf("%lld
",change(lenth));
69     return 0;
70 }
71 
72 int main()
73 {
74     pre();
75     int n;
76     while(scanf("%d",&n)&&n)solve(n);
77     return 0;
78 }

这一定不是最简单的算法，因为我们并不能很好的计算maxn适用的最小值，这在一定程度上浪费了一定的计算力和时间。不过对应付UVA的测试来说足矣。

至于更为简单的算法，我会在参考其他大神的代码后写在我的后续博客里。