kuangbin专题十四 POJ2478 欧拉函数模板题

本文主要是介绍kuangbin专题十四 POJ2478 欧拉函数模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给定一个数n，求在[1,n]这个范围内两两互质的数的个数。
题解：
欧拉函数模板题。
题外话：
哎，数论数学不好，思维不太好真的不适合学，果然只能是到达数论只会GCD的地步吗？凄凉，kuangbin的这套数论基础题我只是会哪些模板题。。其他都阵亡了，哎。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long int 
const int MAXN=1e6+7;
LL euler[MAXN];
int n;
void phi()
{for(int i=1;i<MAXN;i++)euler[i]=i;for(int i=2;i<MAXN;i+=2)euler[i]>>=1;for(int i=3;i<MAXN;i++){if(euler[i]==i){for(int j=i;j<MAXN;j+=i)euler[j]=(euler[j]/i)*(i-1);//先进行除法是为了防止中间数据的溢出   }}
}
int main()
{phi();int n;while(~scanf("%d",&n),n){LL ans=0;for(int i=2;i<=n;i++)ans+=euler[i];printf("%lld\n",ans);}
}

这篇关于kuangbin专题十四 POJ2478 欧拉函数模板题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---