欧拉函数有什么用

欧拉函数有什么用

这篇文章将为大家详细讲解有关欧拉函数有什么用，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

题解：就是求n以内 所有互素的数 的组合数！ 即n以内所有整数的欧拉函数之和！

欧拉函数知识点 可以参考白书。

//2478Accepted4084K235MSC++620B//2478Accepted8000K282MSC++735B#include<iostream>//详细可以参见白书！#include<cstdio>#include<cstring>usingnamespacestd;#defineN1000010intphi[N];voidEula(){inti,j;memset(phi,0,sizeof(phi));//筛法求出N以内的所有n以内的互素数！for(i=2;i<=N;i++)//素数从2开始{if(!phi[i]){for(j=i;j<=N;j+=i){if(!phi[j])phi[j]=j;//赋给该数素因子分解后它的最小素因子！phi[j]=phi[j]/i*(i-1);//后面每一个素因子可以组成的数都用公式刷新下该数的欧拉数！}}}//for(i=2;i<=N;i++)phi[i]+=phi[i-1];第二种方法可以把所有答案打好表！}intmain(){Eula();intn,i;__int64sum;while(scanf("%d",&n),n){sum=0;for(i=2;i<=n;i++)sum+=phi[i];printf("%I64d\n",sum);}return0;}

上面是打表的方法--适用于多数据 而数据小；

以下为求单个 数的欧拉函数--适用于大数据 小规模;

#include<stdio.h>longlongphi(longlonga){longlongtemp=a;for(longlongi=2;i*i<=a;i++)if(a%i==0){while(!(a%i))a/=i;//该数有此素因子，先除完.temp=temp/i*(i-1);//利用公式n/(1-1/p);}if(a!=1)//最后a不是1就是一个素数.temp=temp/a*(a-1);//再利用公式除一下就ok!returntemp;}intmain(){longlonga,b,c;while(scanf("%lld",&a)!=EOF)printf("%lld\n",phi(a));return0;}

关于“欧拉函数有什么用”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。