Minimum Sum LCM（uva10791+和最小的LCM+推理）

L - Minimum Sum LCM

Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu

Submit Status Practice UVA 10791

题意：输入正整数n，<注意n=2^31-1是素数，结果是2^31已经超int，用long long，>找至少两个数，使得他们的LCM为n且要输出最小的和；

思路：既然LCM是n，那么一定是n的质因子组成的数，又要使和最小，那么就是ans+=[质因子]^[个数]+...;

之前我一直超时，感觉都无语了。

转载请注明出处：寻找&星空の孩子

题目链接：UVA 10791

也欢迎来我开的专题刷题。哈哈http://acm.hust.edu.cn/vjudge/contest/view.action?cid=77956#overview

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 #define LL long long
 7 
 8 LL n,sum;
 9 
10 inline LL divisor(LL x)
11 {
12     int t=0,cnt;
13     LL tp;
14     for(int i=2; i<=sqrt(n); i++)
15     {
16         cnt=0;
17         tp=1;
18         if(x%i==0&&i!=n)
19         {
20             while(x)
21             {
22                 if(x%i==0)
23                 {
24                     cnt++;
25                     x=x/i;
26                     tp=tp*i;
27                 }
28                 else {sum+=tp;break;}
29             }
30             t++;
31         }
32         if(!x) break;
33     }
34     if(x>1){sum+=x;t++;}
35  //   printf("sum=%lld
",sum);
36     return t;
37 }
38 
39 int main()
40 {
41 
42     int ca=1;
43     while(scanf("%lld",&n),n)
44     {
45         sum=0;
46         LL m=divisor(n);
47         if(sum==0||m==1)sum=n+1;
48         printf("Case %d: %lld
",ca++,sum);
49     }
50     return 0;
51 }

超时代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 #define LL long long
 6 
 7 LL n,sum;
 8 
 9 inline LL divisor(LL x)
10 {
11     int t=0,cnt;
12     LL tp;
13     for(int i=2; i<=x; i++)//这么写，就超时 了。。。。。
14     {
15         cnt=0;
16         tp=1;
17         if(x%i==0&&i!=n)
18         {
19             while(x)
20             {
21                 if(x%i==0)
22                 {
23                     cnt++;
24                     x=x/i;
25                     tp=tp*i;
26                 }
27                 else {sum+=tp;break;}
28             }
29             t++;
30         }
31         if(!x) break;
32     }
33     return t;
34 }
35 
36 int main()
37 {
38 
39     int ca=1;
40     while(scanf("%lld",&n),n)
41     {
42         sum=0;
43         LL m=divisor(n);
44         if(sum==0||m==1)sum=n+1;
45         printf("Case %d: %lld
",ca++,sum);
46     }
47     return 0;
48 }