程序员人生网站导航

[置顶] HDU 1286 欧拉函数。

栏目：php教程时间：2015-01-05 08:07:00

【科普】甚么是BestCoder？如何参加？

找新朋友

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8077 Accepted Submission(s): 4250

Problem Description

新年快到了，“猪头帮协会”准备弄1个集会，已知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那末该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

Input

第1行是测试数据的组数CN（Case number，1<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。

Output

对每个N，输出1行新朋友的人数，这样共有CN行输出。

Sample Input

2 25608 24027

Sample Output

7680 16016

Author

SmallBeer(CML)

Source

杭电ACM集训队训练赛（VII）

欧拉乃真神人不知道怎样证明的。

其实题意就是这个：在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。例如φ(8)=4，由于1,3,5,7均和8互质。从欧拉函数引申出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

找出和m互质的。

上代码吧。

#include<string.h> #include <stdio.h> int g[32770]; int ouler(int x) { int i,k=1; int m=x; for(i=2;i<=m;i++) { if(m%i==0) { k=k*(i⑴); while(m%i==0) { m=m/i; k*=i; } k/=i; } } return k; //以上是查资料写出的，至于为何是这样的由于证明实在看不懂，我不知道。 } int main() { int ncase,m; scanf("%d",&ncase); while(ncase--) { scanf("%d",&m); printf("%d ",ouler(m)); } return 0; }

------分隔线----------------------------

上一篇 thinkphp小结

下一篇 C++应用程序的入口

------分隔线----------------------------