标签：10 函数 代码 varphi 线性 互质 Euler
引言：由于dsfz的集训老师讲的跟**一样太快了，蒟蒻前去听了洛谷网校@disangan233大佬的讲解，在此重构线性筛Euler函数的证明及代码。
关于Euler函数
- \(Euler\) 函数，同时被称为欧拉函数， 定义： \(\varphi(n)\) 表示 \(\le n\) 且与 \(n\) 互质的数的个数
- 我们规定：\(\varphi(1) = 1\)
Euler函数的性质
- 积性：对于 \(gcd(a,b)=1\) 的两个数 \(a,b\) ， $\varphi(a\times b)=\varphi(a)\times \varphi(b) $.
- 欧拉反演：$\sum_{d|n}\varphi(d) = n $
- 对于任意质数 \(p\)，\(\varphi(p^k)=p^k-p^{k-1}\)
对于Euler函数性质的证明
- 1：根据积性函数的定义可得。
- 2：公式解释：对于每个是 \(n\) 的质因子的数 \(p\)，把他们的 \(\varphi\) 全部加在一起的和是 \(n\).
拿 \(10\) 举例：\(10\) 的全部质因子为 \(\{2,3,5,7,9\}\) ,他们的 \(\varphi\)分别为: \(\{0,1,2,3,4\}\), 加起来就是原数 \(10\).
- 3: 很显然,小于 \(p^k\) 的数中与 \(p\) 不互质的数仅有\(p,2p,3p\dots p^{k-1}p\).总数为 \(p^{k-1}\) 个.
那小于它且与它互质的数的个数就是总数减去 \(p^{k-1}\) 个,即 \(\varphi(p^k)=\) 总数 \(-\ p^{k-1}\),即: \(\varphi(p^k)=p^k-p^{k-1}\)
标签：10,
函数,
代码,
varphi,
线性,
互质,
Euler
From： https://www.cnblogs.com/FrankWKD/p/18679998