欧拉函数

1 欧拉函数的定义和性质

欧拉函数定义：\(\varphi(n)\) 定义为不超过 \(n\) 且与 \(n\) 互质的正整数的个数。

例如，\(n=4\) 时，有 \(1,3\) 与 \(4\) 互质，因此 \(\varphi(4)=2\)；\(n=9\) 时，有 \(1,2,4,5,7,8\) 与 \(9\) 互质，因此 \(\varphi(9)=6\)。

关于欧拉函数，有以下几个公式：

• 如果 \(p,q\) 为互质的正整数，则 \(\varphi(pq)=\varphi(p)\varphi(q)\)。

这个公式说明欧拉函数是积性函数，有以下推理：

设 \(n=\prod \limits_{i=1}^kp_i^{a_i}\)，\(p_i\) 与 \(p_{j}(i \ne j)\) 互质，则有 \(\varphi(n)=\prod \limits_{i=1}^k\varphi(p_i^{a_i})\)。

• 如果 \(n\) 为正整数，则 \(n=\sum \limits_{d \mid n}\varphi(d)\)

证明：

有 \(n\) 个分数：\(\frac{1}{n},\frac{2}{n},\dots,\frac{n}{n}\)。约分这些分数，它们的分子与分母互质。

由于所有分数都不大于 \(1\)，因此分子小于等于分母。如果 \(d \mid n\)，那么分母为 \(d\) 的分数有 \(\varphi(d)\) 个（即与 \(d\) 互质且不超过 \(d\) 的数的数量。因为与 \(d\) 不互质且不超过 \(d\) 的数可以继续与 \(d\) 约分）。

这样分数的总数还可以用 \(\sum \limits_{d \mid n}\varphi(d)\) 表示。

这一性质用于杜教筛。

• 欧拉定理 如果 \(m\) 是正整数，\(a\) 是整数且与 \(m\) 互质，则有：

\(a^\varphi(m) \equiv 1 \pmod m\)。

这一性质常用于欧拉降幂。

2 求欧拉函数的通解公式

设 \(n=\prod \limits_{i=1}^kp_i^{a_i}\)，则 \(\varphi(n)=n\prod \limits_{i=1}^k\frac{p_i-1}{p_i}\)。

所以，求欧拉函数变成了分解质因数。时间复杂度为 \(\mathcal{O}(\sqrt{n})\)。

int phi(int n){
	int res=n,i;
	for(i=2;i*i<=n;++i){
		if(!(n%i)){
			res=res/i*(i-1);n/=i;
			while(!(n%i)){
				n/=i;
			}
		}
	}
	if(n>1){
		res=res/n*(n-1);
	}
	return res;
}

3 用线性筛求 \(1 \sim n\) 的欧拉函数

积性函数都可以使用线性筛。用 \(phi_i\) 表示 \(\varphi(i)\)，\(div_i\) 表示 \(i\) 的最小质因子。结合线性筛质数的代码，第一层循环 \(i\) 枚举所有数，第二层循环 \(j\) 枚举所有质数。分为以下三种情况：

1. \(i\) 为质数

此时 \(phi_i=i-1,div_i=i\)。