欧拉函数有什么用

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

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

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

//     2478    Accepted        4084K   235MS   C++     620B    //      2478    Accepted        8000K   282MS   C++     735B    #include //详细可以参见 白书！#include#includeusing namespace std;#define N 1000010int phi[N];void Eula(){    int i,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]; 第二种方法可以把所有答案打好表！}int main(){    Eula();    int n,i;    __int64 sum;    while(scanf("%d",&n),n)    {        sum=0;        for(i=2;i<=n;i++)            sum+=phi[i];        printf("%I64d\n",sum);    }    return 0;}

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

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

#includelong long phi(long long a){long long temp=a;for(long long i=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!return temp;} int main() {long long a,b,c;while(scanf("%lld",&a)!=EOF)printf("%lld\n",phi(a));return 0;}

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