欧拉函数定义

1N1\sim N中与NN 互质的数的个数被称为欧拉函数,记为ϕ(N)\phi(N)

在算数基本定理中:N=p1c1×p2c2×pmcmN=p_1^{c_1}\times p_2^{c_2}\times\cdots p_m^{c_m},则:

ϕ(N)=N×p11p1×p21p2××pm1pm=N×质数pN(11p)\phi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times \cdots\times\frac{p_m-1}{p_m} = N\times\prod\limits_{质数p\mid N}(1-\frac{1}{p})

证明

p1p_1NN的质因子,1N1\sim Np1p_1的倍数有p1,2P1,3p1,,(N/p1)×p1p_1,2P_1,3p_1,\cdots,(N/p_1)\times p_1,共N/p1N/p_1个。同理。若p2p_2NN的质因子,1N1\sim Np2p_2的倍数有N/p2N/p_2个。这N/p1+N/p2N/p_1 + N/p_2个数中,其中既是p1p_1的倍数,又是p2p_2的倍数的数有N/(p1p2)N/(p_1\cdot p_2) 个。根据容斥原理,NN中去掉p1p_1p2p_2的倍数:

NNp1Np2+Np1p2=N(11p11p2+1p1p2)=N(11p1)(11p2)N-\frac{N}{p_1}-\frac{N}{p_2}+\frac{N}{p_1\cdot p_2}\\ =N(1-\frac{1}{p_1}-\frac{1}{p_2}+\frac{1}{p_1\cdot p_2}) =N\cdot(1-\frac{1}{p_1})(1-\frac{1}{p_2})

类似的,NN的全部质因子都能使用容斥原理实现,得到与NN互质的数的个数。

性质

  1. n>1,1n\forall n > 1,1\sim n中与nn互质的数的和为n×ϕ(n)/2n\times \phi(n)/2
  2. 若a,b互质,则ϕ(ab)=ϕ(a)ϕ(b)\phi(ab)=\phi(a)\cdot \phi(b)

证明性质1

xx为与nn互质的数,则根据更相减损术原理,gcd(n,x)=gcd(n,nx)=1gcd(n,x)=gcd(n,n-x)=1 。故,与n互质的x,n-x成对出现,总和为(x+nx)×ϕ(n)/2=n×ϕ(n)/2(x+n-x)\times \phi(n)/2=n\times \phi(n)/2

性质1证毕。

证明性质2

算数基本定理中:

a=p1c1p2c2pmcma=p_1^{c_1}\cdot p_2^{c_2}\cdots p_m^{c_m}

b=q1d1q2d2qkdkb=q_1^{d_1}\cdot q_2^{d_2}\cdots q_k^{d_k}

ϕ(a)=a(11p1)(11p2)(11pm)\phi(a)=a\cdot(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m})

ϕ(b)=b(11q1)(11q2)(11qk)\phi(b)=b\cdot(1-\frac{1}{q_1})(1-\frac{1}{q_2})\cdots(1-\frac{1}{q_k})

ab\because a、b互质

p1pm,q1qk\therefore p_1\cdots p_m,q_1\cdots q_k各不相同

ab=p1c1p2c2pmcmq1d1q2d2qkdk\therefore a\cdot b=p_1^{c_1}\cdot p_2^{c_2}\cdots p_m^{c_m}\cdot q_1^{d_1}\cdot q_2^{d_2}\cdots q_k^{d_k}

ϕ(ab)=ab(11p1)(11p2)(11pm)(11q1)(11q2)(11qk)\phi(ab)=a\cdot b\cdot(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m})\cdot(1-\frac{1}{q_1})(1-\frac{1}{q_2})\cdots(1-\frac{1}{q_k})

ϕ(ab)=ϕ(a)ϕ(b)\phi(ab)=\phi(a)\cdot \phi(b)

性质

pp是质数

  1. ϕ(p)=p1\phi(p)=p-1
  2. pi,ϕ(i×p)=p×ϕ(i)p\mid i,\phi(i\times p)=p\times\phi(i)
  3. pi,ϕ(i×p)=(p1)×ϕ(i)p\nmid i,\phi(i\times p)=(p-1)\times\phi(i)

证明性质3

因为pp是质数,pp1p11\sim p-1 的每个数都互质,故ϕ(p)=p1\phi(p)=p-1

证明性质4

p\because p为质数,pip\mid i

i=p1c1pcapmcm\therefore i=p_1^{c_1}\cdots p^{c_a}\cdots p_m^{c_m}

ϕ(i)=i×(11p1××(11p)××(11pm)\therefore \phi(i)=i \times (1-\frac{1}{p_1}\times \cdots\times (1-\frac{1}{p})\times \cdots \times (1-\frac{1}{p_m})

i×p=p1c1pca+1pmcmi\times p=p_1^{c_1}\cdots p^{c_a+1} \cdots p_m^{c_m}

ϕ(i×p)=i×p×(11p1)××(11p)××(11pm)\phi(i\times p)=i\times p\times(1-\frac{1}{p_1})\times \cdots \times(1-\frac{1}{p})\times \cdots\times(1-\frac{1}{p_m})

ϕ(i×p)=p×ϕ(i)\therefore \phi(i\times p)=p\times \phi(i)

性质4证毕

证明性质5

p\because p为质数,pip\nmid i

p,i\therefore p,i 互质

ϕ(pi)=ϕ(p)ϕ(i)\therefore \phi(p\cdot i)=\phi(p)\cdot\phi(i)

p\because p为互质

ϕ(p)=p1\therefore \phi(p)=p-1

ϕ(pi)=(p1)×ϕ(i)\therefore \phi(p\cdot i)=(p-1)\times \phi(i)

性质5证毕

代码实现

质因数分解

int phi(int x){//求x的欧拉函数值
	int ans=x;
	for(int i=2;i*i<=x;i++){//分解x的质因数
		if(x%i==0){
			ans=ans/i*(i-1);
			while(x%i==0){
				x/=i;
			}	
		}
	}
	if(x>1) ans=ans/x*(x-1);
	return ans;
}

线性筛

int erla(int n){//利用线性筛更新欧拉函数值
	int cnt=0;//质数个数
	v[0]=v[1]=1;//标记0和1为非质数
	phi[1]=1;//记录1的欧拉函数值为1
	for(int i=2;i<=n;i++){//遍历2~n
		if(!v[i]){//i是质数
			prime[cnt++]=i;//存储i到质数表
			phi[i]=i-1;//性质3: p是质数,phi(p)=p-1
		}
		//遍历质数表
		for(int j=0;j<cnt&&prime[j]*i<=n;j++){
			v[prime[j]*i]=1;//标记质数与i的乘积为非质数
			if(i%prime[j]==0){//性质4:若p%i==0,phi(i*p)=p*phi(i)
				phi[i*prime[j]]=prime[j]*phi[i];
				break;
			}else{//性质5:若p%i!=0,phi(i*p)=(p-1)*phi(i)
				phi[i*prime[j]]=(prime[j]-1)*phi[i];
			}
		}
	}
	return cnt;//返回质数个数
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)