[置顶] HDU 1286 欧拉函数。

发布时间：2020-12-13 20:11:08 所属栏目：PHP教程来源：网络整理

导读：【科普】甚么是BestCoder？如何参加？找新朋友 Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8077Accepted Submission(s): 4250 Problem Description 新年快到了，“猪头帮协会”准备弄1个集会

【科普】甚么是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; }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!