[置顶] HDU 1286 欧拉函数。


 

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

 

 

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » [置顶] HDU 1286 欧拉函数。

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡