定义
欧拉函数 $\varphi(n)$ 表示 $[1,n]$ 中与 $n$ 互质的正整数的个数。例如，$\varphi(p)=p-1,\varphi(1)=1$。
计算式
首先我们证明如下公式（其中 $p$ 为质数）：
$$ \varphi(p^c)=p^c-p^{c-1} $$
这个公式计算的证明十分简单，我们考虑容斥原理。$[1,p^c]$ 中与 $p^c$ 不互质的数的个数有 $\frac{p^c}{p}$ 个，即 $p^{c-1}$ 个，证明完毕。
有了这个式子，在加上欧拉函数是积性函数，我们可以得到计算式：
$$ \text{设}\ n\ \text{的质因子分解式为}\ \prod_{i=1}^k {p_i}^{c_i}\text{，则}\ \varphi(n)=n\prod_{i=1}^k\frac{p_i-1}{p_i} $$
性质
欧拉函数有一个重要的性质：
$$ n=\sum_{d\mid n}\varphi(d)\Longleftrightarrow \varphi\ast 1=\operatorname{ID} $$
这个证明过程在「算法笔记」莫比乌斯反演 中已经涉及，我们在此再次证明一遍：
$$ \begin{aligned} \varphi\ast 1 & =\sum_{d\mid n}\varphi(\frac{n}{d}) \\ & =\sum_{i=0}^c\varphi(p^i) \\ & =1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1) \\ & =p^c \\ & =\operatorname{ID} \\ \end{aligned} $$
求值
线性筛
由于欧拉函数是积性函数，所以可以线性筛，代码如下：
void sieve(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!flg[i]) {
p[++tot] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= tot && i * p[j] <= n; j++) {
flg[i * p[j]] = true;
if (i % p[j] == 0) {
phi[i * p[j]] = phi[i] * p[j];
break;
} else {
phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
}
}单个求值
此时我们只要按照定义来做就行啦！（把质数预处理出来可以加速）
int phi(int x) {
int ans = x;
for (int i = 1; i <= tot && p[i] * p[i] <= x; i++) {
if (x % p[i]) continue;
ans = ans / p[i] * (p[i] - 1);
while (x % p[i] == 0) x /= p[i];
}
if (x > 1) ans = ans / x * (x - 1);
return ans;
}欧拉定理
当我们要求 $a^b\bmod p$ 时，显然指数不能直接对 $p$ 取模，为此我们引入欧拉定理。
- 欧拉定理：若 $\gcd(a,p)=1$，则 $a^{\varphi(p)}\equiv 1\pmod p$。
- 扩展欧拉定理：若 $b > \varphi(p)$，则 $a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}\pmod p$。此处不需要 $p$ 为质数的条件！
因此我们可以得到如下公式：
$$ a^c=\begin{cases} a^{b\bmod\varphi(p)} & \gcd(a,p)=1 \\ a^b & \gcd(a,p)\neq 1,c<\varphi(p) \\ a^{b\bmod\varphi(p)+\varphi(p)} & \gcd(a,p)\neq 1,c\ge\varphi(p) \end{cases} $$
证明的话用同余和完全剩余系之类的就行了？