欧拉函数定义

$1\sim N$中与$N$ 互质的数的个数被称为欧拉函数，记为$\phi(N)$。

在算数基本定理中：$N=p_1^{c_1}\times p_2^{c_2}\times\cdots p_m^{c_m}$，则：

$$\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})$$

证明

设$p_1$ 是 $N$的质因子，$1\sim N$中$p_1$的倍数有$p_1,2P_1,3p_1,\cdots,(N/p_1)\times p_1$,共$N/p_1$个。同理。若$p_2$是$N$的质因子，$1\sim N$中$p_2$的倍数有$N/p_2$个。这$N/p_1 + N/p_2$个数中,其中既是$p_1$的倍数，又是$p_2$的倍数的数有$N/(p_1\cdot p_2)$ 个。根据容斥原理，$N$中去掉$p_1$和$p_2$的倍数:

$$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})$$

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

性质

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

证明性质1

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

性质1证毕。

证明性质2

算数基本定理中：

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

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

$\phi(a)=a\cdot(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m})$

$\phi(b)=b\cdot(1-\frac{1}{q_1})(1-\frac{1}{q_2})\cdots(1-\frac{1}{q_k})$

$\because a、b$互质

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

$\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}$

$\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})$

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

性质

若$p$是质数

3. $\phi(p)=p-1$
4. 若$p\mid i,\phi(i\times p)=p\times\phi(i)$
5. 若$p\nmid i,\phi(i\times p)=(p-1)\times\phi(i)$

证明性质3

因为$p$是质数，$p$与$1\sim p-1$ 的每个数都互质，故$\phi(p)=p-1$。

证明性质4

$\because p$为质数，$p\mid i$

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

$\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\times p=p_1^{c_1}\cdots p^{c_a+1} \cdots p_m^{c_m}$

$\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})$

$\therefore \phi(i\times p)=p\times \phi(i)$

性质4证毕

证明性质5

$\because p$为质数，$p\nmid i$

$\therefore p,i$ 互质

$\therefore \phi(p\cdot i)=\phi(p)\cdot\phi(i)$

$\because p$为互质

$\therefore \phi(p)=p-1$

$\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.