定义
$\varphi(x)$ 指对于 $\forall i\in [1,x]$ ，满足 $\gcd(i,x)=1$ 的 $i$ 的个数。
也就是小于等于 $x$ 的正整数中与其互质的数的个数。
基本推论
$\varphi(x)=x-1\quad(x\in \mathbb{P})$
$ \begin{aligned} \varphi(p^k)& =p^k-p^{k-1} \quad(p\in \mathbb{P},k\in \Z^*) \\ &= p^k(1-\frac{1}{p})\quad(p\in \mathbb{P},k\in \Z^*)\end{aligned}$
这是因为只有当一个数不包含质数 $p$ ，才可能与 $x$ 互质。而包含质数 $p$ 的数一共有$ p^{k-1} $个，即 $1×p、2×p、3×p、…、p^{k-1}×p$ ，把它们去除，剩下的就是与n互质的数。
若 $x=p_1 \times p_2 \quad (\gcd(p_1,p_2)=1)$
则 $\varphi(x)=\varphi(p_1p_2) = \varphi(p_1)\varphi(p_2)$
证明较为复杂。
由上式推广
有
$n=p_1^{k_1}p_2^{k_2}…p_x^{k_x}\quad(p_1,p_2… p_n\in \mathbb{P})$
$ \begin{aligned} \varphi(n)&=\varphi(p_1^{k_1})\varphi(p_2^{k_2})…\varphi(p_x^{k_x})\\ &= p_1^{k_1}p_2^{k_2}…p_x^{k_x}(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_x}) \\ &= n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_x}) \end{aligned}$
于是我们就得到了欧拉函数的通项
即
由通项我们可以推导，若 $y|x$ ，则
$\varphi(x\times y)=\varphi(x) \times y$
由通项我们还可以推出
$\varphi(n!)=\begin{cases} \varphi((n-1)!)\times(n-1)&n\in \mathbb{P} \\\varphi((n-1)!)\times n & n\notin\mathbb{P} \end{cases}$
可以在 $O(n)$ 时间内求解 $\varphi(n!)$ 。
计算
- 单个求法
在上文中我们推导出了欧拉函数通项，
配合质数筛可以在 $O(因子个数)$ 内求出 $\varphi(n) $。
int phi(int x){
int ans=x;
for(int i=1;i<=cnt&&prime[i]*prime[i]<=x;++i){
if(x%prime[i]) continue;
ans=ans/prime[i]*(prime[i]-1);
while(x%prime[i]==0) x/=prime[i];
}
if(x>1) ans=ans/x*(x-1);
return ans;
}
- 多个求法
然而我们在某些时候需要求出连续区间内的所有 $\varphi(i)$ 值，这时候上述求法的复杂度就有些劣
涉及 $10^6$ 及以上的数据时容易被卡常，因此我们需要更快的方式。
涉及到线性，质数，我们可以自然联想到欧拉筛。
回忆一下欧拉筛的实现步骤：
- 遍历每个 $x$ ，观察是否为质数。
- 使用先前筛出的质数和遍历到的 $x$ ，筛掉接下来的合数。
我们知道，欧拉筛的过程是线性的，也就是每个数最多遍历一遍，利用这个性质，我们可以做到线性求解。
第一步中，对于 $x\in \mathbb{P}$ ，$\varphi(x)=x-1$
第二步中，对于合数，我们发现：
对于任意 $y=x*p\quad(p\in \mathbb{P} \&x> p)$, 总有
$\varphi(y)=\varphi(x)\times \varphi(p)\quad(p\nmid x)$
$\varphi(y)=\varphi(x)\times p\quad(p\mid x)$
然后我们就可以代码实现。
void init(){
isp[0]=isp[1]=1;phi[1]=1;
for(int i=2;i<N;++i){
if(!isp[i]) pri[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&pri[j]*i<=N;++j){
isp[pri[j]*i]=1;
if(i%pri[j]) phi[pri[j]*i]=phi[i]*phi[pri[j]];
else phi[pri[j]*i]=pri[j]*phi[i];
if(i%pri[j]==0) break;
}
}
//for(int i=1;i<N;++i) sum[i]=sum[i-1]+phi[i];
}