【NOIp复习】欧拉函数

基础

欧拉函数phi(x)是指从1…x与x互质的自然数的个数性质1：如果p是质数，phi(p)=p-1,phi(p^k)=p^k-p^(k-1)性质2：如果p,k互质，phi(p*k)=phi(p)*phi(k)

然后就得到了百度百科的那个通式： phi(x)=x*(1-1/p1)…(1-1/pn);

所以任何一个数，只需要分解质因数，把每个p^k都乘起来就是这个数的欧拉函数值了。在C++中这样表达：

int phi(int n){ int m=(int)sqrt(n+0.5);//筛质数的上界 int ans=n; for(int i=2;i<=m;i++) if(n&i==0){//找到n的质因数i ans=ans/i*(i-1); while(n%i==0) n/=i;//一直把n除到没有因数i为止 } if(n>1) ans=ans/n*(n-1);//phi(1)=1,so... return ans; }

筛法：

int phi_table(int n){ for(int i=1;i<=n;i++) phi[i]=0; phi[1]=1;//特别定义 for(int i=2;i<=n;i++) if(!phi[i]){ for(int j=1;j<=n;j+=i){ if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } }

奇技淫巧的应用

不大于x的与x互质的数和为phi(x)*x/2

例题整理

法雷级数由一系列不能约分的分数按递增的顺序排列组成，现在让你求出第n项法雷级数包含多少个分数。让找出从（0,0）点出发到（n，n）点之间只经过两点的直线的数目。对于给定的整数L，找出L能整除最短的全8序列的长度，做为Bob的幸运数字。记P_i表示正整数i的质因数集合. 已知正整数n，求满足下列条件的有序正整数对(a,b)的数目： (1)1<=a<=b<=n; (2)t为a,b的最大公约数,P_t是P_n的子集.POJ 3696（文章里面说的“欧拉公式”实际上指欧拉定理：a^phi(m)≡1(mod m)，所以同余方程a^x≡1(mod m)的解一定是phi(m)的因数）[HDU 2588] 计算1~n中有多少个数和n的最大公因数比m大（将n分解为a*b，如果gcd(n,x)=a那么x=a*d，其中d是一个比b小的与b互质的数。所以确定了a过后phi(b)就是x的个数了，从m开始（或者从sqrt(n)开始，看哪个更小）枚举）

好难啊！完全不会！

转载于:https://www.cnblogs.com/leotan0321/p/6081392.html