首页 > 代码库 > 51NOD-1136 欧拉函数
51NOD-1136 欧拉函数
基准时间限制：1 秒 空间限制：131072 KB
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler‘s totient function、φ 函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。
Input
输入一个数N。(2 <= N <= 10^9) Output
输出Phi(n)。 Input示例
8 Output示例
4
解题思路：
这道题就是求出在区间[1,n-1]中有m个数与n互质，求出m的值 （互质：2个数之间只有1是他们的公约数 ）
欧拉函数的求法：如果a1,a2,a3……是n的质因子数，那么
m=n*(1-1/a1)*(1-1/a2)*(1-1/a3)……
1 #include<stdio.h> 2 int main() { 3 long long n,i,j,sum; 4 5 while(scanf("%lld",&n)!=EOF) { 6 sum=n; 7 for(i=2; i*i<=n; i++) { 8 if(n%i==0) { 9 sum=sum/i*(i-1);10 while(n%i==0) {11 n/=i;12 }13 }14 }15 if(n>1) {16 sum=sum/n*(n-1);17 }18 printf("%lld\n",sum);19 }20 21 return 0;22 }
51NOD-1136 欧拉函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。