Minimum Sum LCM UVA

题解：根据唯一分解定理，设唯一分解式 n=a₁^p1 ......，不难发现每个a₁^p1作为单独的一个整数时最优。

注意：①n=1时,ans=2；②n只有一个因子时需要加个1③n=2³¹-1时不要溢出

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 
 9 int n,num;
10 ll sum,temp;
11 
12 void inite(){
13     sum=0,num=0;
14     temp=n;
15     for(int i=2;i<=sqrt(n)+1;i++){
16         if(temp%i) continue;
17         num=num+1;
18         ll tsum=1;
19         while(temp%i==0) { temp=temp/i; tsum*=i; }
20         sum=sum+tsum; 
21     }
22 }
23 
24 int main()
25 {   int kase=0;
26     while(~scanf("%d",&n)&&n){
27         inite();
28         if(num==0) sum=(ll)n+1;
29         else if(num==1||temp!=1) sum=sum+temp;       //num==1说明出了1和它本身之外只有一个质因子，temp!=1说明在另一半只有一个质因子。
30         printf("Case %d: %lld
",++kase,sum);
31     }
32     return 0;
33 }