欧拉函数
定义
我们定义 \(\varphi (x)\) 为 小于 \(x\) 的正整数中与 \(x\)
互质的数的个数，称作欧拉函数。数学方式表达就是
但需要注意，我们定义 \(\varphi(1) = 1\) 。
性质
-
若 \(x\) 为质数，\(\varphi(x) = x - 1\) 。
证明：这个很显然了，因为除了质数本身的数都与它互质。
-
若 \(x = p^k\) （ \(p\) 为质数， \(x\)
为单个质数的整数幂），则 \(\varphi(x) = (p - 1) \times p ^ {k - 1}\) 。证明：不难发现所有 \(p\) 的倍数都与 \(x\)
不互质，其他所有数都与它互质。\(p\) 的倍数刚好有 \(p^{k-1}\) 个（包括了 \(x\) 本身）。
那么就有 \(\varphi(x) = p^k - p^{k-1} = (p - 1) \times p^{k- 1}\) 。
-
若 \(p, q\) 互质，则有 \(\varphi(p \times q) = \varphi(p) \times \varphi(q)\) ，也就是欧拉函数是个积性函数。
证明 ：
如果 \(a\) 与 \(p\) 互质 \((a<p)\) ， \(b\) 与 \(q\)
互质 \((b<q)\) ， \(c\) 与 \(pq\) 互质 \((c<pq)\) ，则
\(c\) 与数对 \((a,b)\) 是一一对应关系。由于 \(a\) 的值有
\(\varphi (p)\) 种可能， \(b\) 的值有 \(\varphi(q)\)
种可能，则数对 \((a,b)\) 有 \(φ(p)φ(q)\) 种可能，而 \(c\)
的值有 \(φ(pq)\) 种可能，所以 \(φ(pq)\) 就等于 \(φ(p)φ(q)\)
。具体来说这一条需要 中国剩余定理 以及 完全剩余系
才能证明，感性理解一下它的思路吧。 -
对于一个正整数 \(x\) 的质数幂分解 \(\displaystyle x = {p_1}^{k_1} \times {p_2}^{k_2} \times \cdots \times {p_{n} }^{k_n} = \prod _{i=1}^{n} {p_i}^{k_i}\) 。
\(\displaystyle \varphi(x) = x \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots \times (1 - \frac{1}{p_n}) = x\prod_{i=1}^{n} (1-\frac{1}{p_i})\)
证明：
我们考虑用前几条定理一起来证明。
\(\begin{aligned} \varphi(x) &= \prod_{i=1}^{n} \varphi(p_i^{k_i}) \\ &= \prod_{i=1}^{n} (p_i-1)\times {p_i}^{k_i-1}\\ &=\prod_{i=1}^{n} {p_i}^{k_i} \times(1-\frac{1}{p_i})\\ &=x \prod_{i=1}^{n} (1-\frac{1}{p_i}) \end{aligned}\)
-
若 \(p\) 为 \(x\) 的约数（ \(p\) 为质数, \(x\) 为任意正整数），我们有 \(\varphi(x \times p) = \varphi(x) \times p\) 。
证明：
我们利用之前的第 \(4\) 个性质来证明就行了。
不难发现 \(\displaystyle \prod _{i=1}^{n} (1 - \frac{1}{p_i})\) 是不会变的，前面的那个 \(x\) 会变成 \(x \times p\) 。
所以乘 \(p\) 就行了。
-
若 \(p\) 不是 \(x\) 的约数（ \(p\) 为质数, \(x\)
为任意正整数），我们有 \(\varphi(x \times p) = \varphi(x) \times (p - 1)\) 。证明 ：\(p, x\) 互质，由于 \(\varphi\) 积性直接得到。
求欧拉函数
求解单个欧拉函数
我们考虑质因数分解，然后直接利用之前的性质 \(4\) 来求解。
快速分解的话可以用 \(PollardRho\) 算法。
求解一系列欧拉函数
首先需要学习 线性筛，我们将其改一些地方。
质数 \(p\) 的 \(\varphi(p) = p-1\) 。
对于枚举一个数 \(i\) 和另外一个质数 \(p\) 的积 \(x\) 。
我们在线性筛，把合数筛掉会分两种情况。
- \(p\) 不是 \(i\) 的一个约数，由于性质 \(5\) 就有
\(\varphi(x) = \varphi(i) \times (p - 1)\) 。 - \(p\) 是 \(i\) 的一个约数，此时我们会跳出循环，由于性质 \(6\)
有 \(\varphi(x) = \varphi(i) \times p\) 。
代码实现
bitset<N> is_prime; int prime[N], phi[N], cnt = 0;
void Init(int maxn) {
is_prime.set(); is_prime[0] = is_prime[1] = false; phi[1] = 1;
For (i, 2, maxn) {
if (is_prime[i]) phi[i] = i - 1, prime[++ cnt] = i;
For (j, 1, cnt) {
int res = i * prime[j];
if (res > maxn) break;
is_prime[res] = false;
if (i % prime[j]) phi[res] = phi[i] * (prime[j] - 1);
else { phi[res] = phi[i] * prime[j]; break; }
}
}
}
欧拉定理
若正整数 \(a\) 与 \(m\) 互质，则
\(a^{\varphi(m)} \equiv 1\pmod m\)
扩展欧拉定理
\(a^b\equiv \begin{cases} a^{b \bmod \varphi(p)} & a \bot p\\ a^b & a \not \bot p,b<\varphi(p)\\ a^{b \bmod \varphi(p) + \varphi(p)} & a \not \bot p,b\geq\varphi(p) \end{cases} \pmod p\)
证明看 这里，有点难证，记结论吧。
这个常常可以用于降幂这种操作。