1040 最大公约数之和

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<stdlib.h>
 5 #include<queue>
 6 #include<string.h>
 7 #include<math.h>
 8 using namespace std;
 9 typedef long long LL;
10 bool prime[100005];
11 int ans[100000];
12 LL phi(LL n,int cn);
13 int main(void)
14 {
15         int i,j;
16         int cn = 0;
17         for(i = 2; i  <= 1005; i++)
18         {
19                 if(!prime[i])
20                 {
21                         for(j = i; (i*j) <= 100005; j++)
22                         {
23                                 prime[i*j] = true;
24                         }
25                 }
26         }
27         for(i = 2; i <= 100005; i++)
28         {
29                 if(!prime[i])
30                         ans[cn++] = i;
31         }
32         LL n;
33         scanf("%lld",&n);
34         LL sum = 0;
35         for(i = 1; i <= sqrt(1.0*n); i++)
36         {
37                 if(n%i==0)
38                 {
39                         LL ak = n/i;
40                         if(ak==i)
41                         {
42                                 sum += phi(n/i,cn)*(LL)i;
43                         }
44                         else
45                         {
46                                 sum += phi(n/i,cn)*(LL)i+phi(n/ak,cn)*(LL)ak;
47                         }
48                 }
49         }
50         printf("%lld\n",sum);
51         return 0;
52 }
53 LL phi(LL n,int cn)
54 {
55         LL ap = sqrt(1.0*n);
56         int i,j;
57         LL t = n;
58         int f = 0;
59         int flag = 0;
60         while(t>1)
61         {
62                 while(t%ans[f]==0)
63                 {
64                         if(flag == 0)
65                         {
66                                 flag = 1;
67                                 n/=ans[f];
68                                 n*=(ans[f]-1);
69                         }
70                         t /= ans[f];
71                 }
72                 f++;flag = 0;
73                 if(ans[f]*ans[f]>t)
74                         break;
75         }
76         if(t>1)
77         {
78                 n/=t;
79                 n*=(t-1);
80         }
81         return n;
82 }