題意：
給定N(int) 求 ∑gcd(i,N) 1<=i<=N
又是數(shù)論題。。我太菜了 想了很久
做法：
直接求不會(huì)
只能考慮 對(duì)于gcd(M,N)=i 有Ci個(gè)M滿足此式 答案便是∑(Ci*i)
gcd(M,N)=i <=> gcd(M/i,N/i)=1
而求gcd(M/i,N/i)=1 有多少個(gè)M/i滿足 這便是歐拉函數(shù)Phi()的定義
所以就轉(zhuǎn)化為了求Phi(N/i)
枚舉每個(gè) M|N 求出Phi(N/i) 答案便是 ∑(Phi(N/i)*i)
那么如何枚舉每個(gè) M|N 呢？
很簡(jiǎn)單 枚舉1到sqrt(N)的所有整數(shù)，所有的約數(shù)便是 j|N (N/j)|N
這樣就搞定了
1 #include <cstdio>
2 #include <cmath>
3 #define n 50005
4 int p[n],N;
5 bool mk[n];
6 inline void mkprime()
7 {
8 for (int i=2;i<n;++i)
9 if (!mk[i])
10 for (int j=i<<1;j<n;j+=i)
11 mk[j]=1;
12 for (int i=2;i<n;++i)
13 if (!mk[i]) p[++p[0]]=i;
14 }
15 inline int Phi(int u)
16 {
17 int phi=u;
18 for (int i=1;i<=p[0]&&p[i]*p[i]<=u;++i)
19 if (u%p[i]==0)
20 {
21 phi=phi/p[i]*(p[i]-1);
22 for (;u%p[i]==0;u/=p[i]);
23 }
24 if (u>1) phi=phi/u*(u-1);
25 return phi;
26 }
27 int main()
28 {
29 mkprime();
30 for (;scanf("%d",&N)!=EOF;)
31 {
32 long long ret=0;
33 for (int i=1,up=(int)sqrt((double)N);i<=up;++i)
34 if (N%i==0)
35 {
36 ret+=(N/i)*(long long)Phi(i);
37 if (i*i!=N) ret+=i*(long long)Phi(N/i);
38 }
39 printf("%I64d\n",ret);
40 }
41 return 0;
42 }
43