首页 > 代码库 > uva10791

uva10791

2024-07-06 01:04:50   223人阅读

解题思路：如果n是质数，结果为n+1；

              n=1，结果为2；

             如果n是一个质数的幂，结果为n+1；

             否则把n质因数分解，则所有的质因数的幂次的和，即为所求。

假设n=p1^e1*p2^e2*p3^e3...pk^ek

结果为：p1^e1+p2^e2+....pk^ek;

 1 //Accepted    0 KB    12 ms
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 const int MAXN =1<<17;
 6 int pri[MAXN];
 7 int cnt;
 8 void prime()
 9 {
10     for (int i=2;i<(int )sqrt(1.0*MAXN);i++)
11     {
12         if (!pri[i])
13         {
14             for (int j=i*i;j<MAXN;j+=i)
15             pri[j]=1;
16         }
17     }
18     for (int i=2;i<MAXN;i++)
19     {
20         if (!pri[i])
21         {
22             pri[cnt++]=i;
23         }
24     }
25 }
26 int p[100],pNum[100];
27 int num;
28 long long  slove(int n)
29 {
30     int i=0;
31     long long ans=0;
32     int tempn=n;
33     num=0;
34     memset(p,0,sizeof(p));
35     memset(pNum,0,sizeof(pNum));
36     while (i<cnt && (long long )pri[i]*pri[i]<=n)
37     {
38         if (n%pri[i]==0)
39         {
40             while (n%pri[i]==0)
41             {
42                 n/=pri[i];
43                 pNum[num]++;
44             }
45             p[num++]=pri[i];
46         }
47         i++;
48     }
49     if (n!=1)
50     {
51         p[num]=n;
52         pNum[num++]=1;
53     }
54     if (num==1)
55     {
56         ans=(long long )tempn+1;
57         return ans;
58     }
59     int temp;
60     for (int i=0;i<num;i++)
61     {
62         temp=1;
63         for (int j=0;j<pNum[i];j++)
64         temp*=p[i];
65         ans+=temp;
66     }
67     return ans;
68 }
69 int n;
70 int main()
71 {
72     int t=0;
73     prime();
74     while (scanf("%d",&n),n)
75     {
76         long long ans=slove(n);
77         if (n==1) ans=2;
78         printf("Case %d: %lld\n",++t,ans);
79     }
80     return 0;
81 }
View Code

 


联系
我们