Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

Pku 2480 Longge's Problem

题意:
给定N(int)  求 ∑gcd(i,N) 1<=i<=N

又是数论题。。我太菜了 想了很久

做法:
直接求不会
只能考虑  对于gcd(M,N)=i 有Ci个M满足此式 答案便是∑(Ci*i)
gcd(M,N)=i  <=> gcd(M/i,N/i)=1
而求gcd(M/i,N/i)=1 有多少个M/i满足 这便是欧拉函数Phi()的定义
所以就转化为了求Phi(N/i)

枚举每个 M|N  求出Phi(N/i)  答案便是 ∑(Phi(N/i)*i)
那么如何枚举每个  M|N 呢?
很简单 枚举1到sqrt(N)的所有整数,所有的约数便是 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 

posted on 2010-04-22 12:18 jsn1993 阅读(428) 评论(0)  编辑 收藏 引用 所属分类: Math


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理