欧拉函数学习笔记

欧拉函数，一般写作 $\varphi$ 或者 $\phi$。$\varphi(x)$ 表示的是 $[1,x]$ 区间内有多少个数与 $x$ 互质（最大公因数为 1）。

• 性质 1：当 $p$ 为质数时 $\varphi(p)=p-1$。

• 性质 2：设 $p_i$ 表示 $x$ 的第 $i$ 个质因子，$n$ 表示 $x$ 的质因子个数，则 $\varphi(x)=x\prod\limits_{i=1}^n\frac{p_i-1}{p_i}$。

只有不是 $x$ 的质因子的倍数的数才和 $x$ 互质；

第一个质因子的倍数共有 $x\times \frac{1}{p_i}$ 个，那么和第一个质因子互质的数就有 $x\times \frac{p_i-1}{p_i}$ 个；

这 $x\times \frac{p_i-1}{p_i}$ 个数里，和第二个质因子互质的个数又有 $x\times \frac{p_i-1}{p_i}$ 个；

一直乘下去，便得到 $\varphi(x)=x\prod\limits_{i=1}^n\frac{p_i-1}{p_i}$。

• 性质 3：$\varphi(xy)=\varphi(x)\varphi(y)\times\frac{\gcd(x,y)}{\varphi(\gcd(x,y))}$

考虑 $\varphi(x)=x\prod\limits_{i=1}^n\frac{p_i-1}{p_i}$，观察到 $\varphi(x)\varphi(y)=xy\prod\limits_{i=1}^m\frac{p_i-1}{p_i}$ 多乘了 $\gcd(x,y)$ 的质因子的 $\frac{p_i-1}{p_i}$，所以要除掉 $\frac{\varphi(\gcd(x,y))}{\gcd(x,y)}$。

• 性质 4：若 $p$ 是 $x$ 的一个质因子，$\varphi(xp)=\varphi(x)\cdot p$。

若 $gcd(x,y) = 1$，$gcd(x,y+x) = 1$。

• 性质 5：$\sum\limits_{d|n}\varphi(d)=n$

设 $n$ 个分数 $\dfrac{1}{n}\dfrac{2}{n}\dfrac{3}{n}...\dfrac{n}{n}$，全部化到最简后，分母显然全部是 $n$ 的因子，而分母 $d$ 有 $\varphi(d)$ 个，又因为分母总共有 $n$ 个，所以得证。

以上性质的具体证明可以看这篇文章。

有了这些特质，我们便可以结合欧拉筛来实现 $O(n)$ 求 $x\in[1,n]$ 的 $\varphi(x)$ 了。

代码如下：

int fhi[100005];
bool nop[100005];
int tot,prime[100005];
int n;

void init()
{
	nop[0]=true; // 0 不是质数
	nop[1]=true; // 1 不是质数
	fhi[1]=1; // 1 和 1 互质（
	for(int i=2;i<=n;i++)
	{
		if(!nop[i])
		{
			prime[++tot]=i;
			fhi[i]=i-1; // 是一个质数，fhi(i) 满足性质 1
		}
		for(int j=1;j<=tot;j++)
		{
			if(i*prime[j]>n)
			{
				break;
			}
			nop[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				fhi[i*prime[j]]=fhi[i]*prime[j]; // prime[j] 是 i 的一个质因子，满足性质 4
				break;
			}
			fhi[i*prime[j]]=fhi[i]*fhi[prime[j]]; // i 和 prime[j] 互质，满足性质 3
		}
	}
}

练习题目

P2158 [SDOI2008] 仪仗队

P2398 GCD SUM

P1390 公约数的和

P2568 GCD

LOJ 6179 Pyh 的求和