NYOJ570---欧拉函数求和

NYOJ570---欧拉函数求和

570 欧拉函数求和

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

题目描述很简单，求出：

（PS:上面式子的意思是大于0小于n并且能整除n的所有d的欧拉函数值之和）。

输入

每行一个数n（n<2^31)，输入以文件结尾结束。

输出

每个结果占一行。

样例输入

1

2

12

样例输出

0

1

8

/**************Author:jiabeimuweiTimes:0msSources:NYOJ570**************/ #include#include#include#includeusing namespace std;#define LL long longLL Euler(LL n){ LL sum=n; for(LL i=2; i*i<=n; i++) { if(n%i==0) { while(n%i==0) n=n/i; sum=sum/i*(i-1); } } if(n>1) sum=sum/n*(n-1); return sum;}int main(){ int n; while(~scanf("%d",&n)) { LL sum=0; for(int i=1; i*i<=n; i++) { if(n%i==0) { if(i!=n) sum+=Euler(i); if(i*i!=n&&i!=1) sum+=Euler(n/i); } } printf("%lld\n",sum); } return 0;}学长的比较好的代码：#includeint Eular(int n){ int i; int ans=n; for(i=2; i*i<=n; ++i) { if(n%i==0) { ans-=ans/i; while(n%i==0) n=n/i; if(n==1) break; } } if(n!=1) ans-=ans/n; return ans;}int main(){ int i, j, k, n, x; while( ~scanf("%d",&n) ) { int sum = 0; if(n==1) { puts("0"); continue; } for(i=1; i*i<=n; i++) { if(n%i==0) { sum+=(Eular(i)); if( i!=1 && i*i!=n ) sum+=(Eular(n/i)); } } printf("%d\n",sum); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。