欧拉函数
欧拉函数:对于正整数n,欧拉函数是小于等于n的数中与n互质的数的数目。
一般用φ(x)表示,特殊的,φ(1)=1。
其中pi表示x的质因子。
理解:举个例子:12 (1,2,3,4,5,6,7,8,9,10,11,12),它的质因子有2,3;
有(1/2))的数是2的倍数(2,4,6,8,10,12),有(1-(1/2))的数字不是2的倍数(1,3,5,7,9,11),在这些数中有(1/3)的数是3的倍数(3,9),只有(1-(1/2)*(1-(1/3))的数字(1,5,7,11)既不是2的倍数也不是3的倍数,即与12互质。
那么便好理解这个公式了,x中有p1,p2,p3,...,pn个质因数,
即有x*(1-(1/p1))*(1-(1/p2))*(1-(1/p3)...*(1-(1/pn)个数字与x互质。
性质:
积性函数:φ(a*b)=φ(a)*φ(b)(a与b互质);
证明:
因为a与b互质,所以bi与ai无重复,所以
φ(a)*φ(b)=
(pi为a和b的质因子)=φ(a*b);
引理:
1.如果n为某个素数p,则φ(p)=p-1;
证明:如果p为素数,比p小的数都与p互质,共有(p-1)种。
2.如果n为某个素数p^a^,则φ(n)=(p-1)*p^a-1^;
证明:因为p是质数,所以q^a^的质因子只有q;所以在p^a^中有p^a^个数,减去q的所有倍数,即使答案。
φ(n)=p^a^-p^a-1^=(p-1)*p^a-1^.
3.即欧拉函数是积性函数。
欧拉定理:若a与m互质,则a^φ(n)^mod m=1mod m。
证明:
求欧拉函数:
1.若单纯的求某个数的欧拉函数,直接从(1~sqrt(n))枚举即可。
2.埃氏筛。
tp=phi=m;
for (i=2;i*i<=m;++i)
{
if(tp%i==0)
{
phi=phi-phi/i;
while(tp%i==0) tp/=i;
}
}
if(tp>1)
phi=phi-phi/tp;
3.欧拉筛.
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=40010;
int n;
int phi[maxn],prime[maxn],tot,ans;
bool mark[maxn];
void getphi()
{
int i,j;
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!mark[i])
{
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot;j++)
{
if(i*prime[j]>n) break;
mark[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[j]*prime[j];break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int main()
{
cin>>n;
getphi();
for(int i=1;i<=n;i++)
printf("%d ",phi[i]);
return 0;
}