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

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

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\n",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\n",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\n",ca++,sum);
46     }
47     return 0;
48 }