这篇文章将为大家详细讲解有关欧拉函数有什么用，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
题解：就是求n以内 所有互素的数 的组合数！ 即n以内所有整数的欧拉函数之和！
欧拉函数知识点 可以参考白书。
计算
安全
数据库
网络和加速
企业服务
// 2478 Accepted 4084K 235MS C++ 620B
// 2478 Accepted 8000K 282MS C++ 735B
#include <iostream>//详细可以参见 白书！
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000010
int 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;
}上面是打表的方法--适用于多数据 而数据小；
以下为求单个 数的欧拉函数--适用于大数据 小规模;
#include<stdio.h>
long 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;
}关于“欧拉函数有什么用”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://www.xuebuyuan.com/3265895.html
