欧拉函数的积性证明及线性筛

欧拉函数的积性证明

欧拉函数即(varphi)函数

以下两段是从大佬那里淘来的证明

同样的，(tperp nmLeftrightarrow tperp n,tperp mLeftrightarrow(tmod n)perp n,(tmod m)perp m)，所以每个 ([1, nm])之间的与(nm)互质的数(t)都可以对应到一个([1,n])的与(n)互质的数 (tmod n)和一个([1,m])的与(m)互质的数(tmod m)。

并且根据中国剩余定理，这种对应是一一对应的（即已知 (aperp n, bperp m)后可以唯一确定一个([1,nm])之间的(t)使得(tmod n=a, tmod m=b)，且(tperp nm)）。因此 (varphi(nm)=varphi(n)varphi(m)) 。

---

然而我看不懂……还是从定义上来证明吧！

假设有两个互质的正整数(n,m)，则

[varphi(n)=nprod(1-frac{1}{p_i}) ]

[varphi(m)=mprod(1-frac{1}{p_{i'}}) ]

[varphi(n)varphi(m)=nprod(1-frac1{p_i})mprod(1-frac1{p_{i'}})=nmprod(1-frac1{p_i})prod(1-frac1{p_{i'}}) ]

因为(n,m)互质，所以(p_i)和(p_{i'})各各都不相同，且都是(nm)的质因子

因此就可以推出(varphi(nm)=varphi(n)varphi(m))

至此，积性函数的性质得证。但是由上面的证明可知，(n,m)必须要互质才可以满足欧拉函数是积性函数，由此可见欧拉函数不是完全积性函数

线性筛欧拉函数

友情提示：建议先学习线性筛素数再来学习，在此不会讲线性筛的基本操作

线性筛欧拉函数可以分为三种情况：

1. (i)是质数时，(varphi(i)=n-1)，根据质数的性质，在(1sim i)中，有(i-1)个与(i)互质的数，所以质数(i)的欧拉函数就是(i-1)
2. (imod p[j] eq 0)时，说明(i)和(p[j])互质，(varphi(i imes p[j])=varphi(i)varphi(p[j]))（因为(p[j])是质数，所以(varphi(p[j]))也可以写成(p[j]-1)，代码里写的是(varphi(p[j]))）
3. (imod p[j]=0)时，(varphi(i*p[j])=varphi(i)*p[j])（从欧拉函数定义来证明，表示我也不会）

代码如下：

int phi[A], p[A], cnt;
//phi欧拉函数，p质数数组，cnt记录质数个数 
bool vis[A];//为1即为合数，为0则为质数 

void getphi() {
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) p[++cnt] = i, phi[i] = i - 1;
		for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
			vis[i * p[j]] = 1;
			if (i % p[j] == 0) { phi[i * p[j]] = phi[i] * p[j]; break; }
			else phi[i * p[j]] = phi[i] * phi[p[j]];//互质，利用欧拉函数的积性 
		}
	}
}