求 \(a^b \bmod m, b\le 10^{200000}\)。
首先引入三种可以通过取模缩小幂指数的方法。
- 费马小定理：当 \(a,p\in \mathbb{Z},\space p\) 为质数且 \(p\nmid a\) 时，\(a^{p-1}\equiv 1(\bmod\space p)\)，所以有 \(a^b\equiv a^{b\bmod (p-1)}(\bmod\space p)\)；
- 欧拉定理：当 \(a,m\in\mathbb{Z},\space a,m\) 互质时，\(a^{\varphi(m)}\equiv 1(\bmod\space m)\)，其中欧拉函数 \(\varphi(n)\) 为 \([1,n]\) 中与 \(n\) 互质的数的个数。由此， \(a^b=a^{b\bmod\varphi(m)}(\bmod\space m)\)；
- 扩展欧拉定理：当 \(a,m\in\mathbb{Z}\) 时，
\( a^b=\left\{ \begin{aligned} & a^b&, b\le\varphi(m) \\\ & a^{b\bmod\varphi(m)+\varphi(m)},&b>\varphi(m) \end{aligned} \right.(\bmod\space m) \)。
此题没有给出 \(a,m\) 间的互质关系，只能采用扩展欧拉定理解决。只需求出 \(\varphi(m)\) 即可，我们可以采取分解质因数的方法，结合欧拉函数公式
\(
\varphi(n)=\left\{
\begin{aligned}
& 1 &,n=1 \\\
& n\prod\limits_{i=1}^{k}(1-\dfrac{1}{p_i}) &,n\neq 1
\end{aligned}
\right.
\)
来 \(O(\sqrt{m})\) 地求解。公式里的 \(k,p_i\) 来自 \(n\) 的唯一分解 \(n=\prod\limits_{i=1}^{k} p_i,\space p_i\) 为质数。
int phi = m;
for (int p = 2; n > 0; p++) {
if (n % p != 0) continue;
phi -= phi / p; // 公式中 (1-1/p) 的变形
while (n % p == 0) n /= p;
}
下面延伸介绍一下欧拉函数的知识。除了公式，还有五种方法可以计算欧拉函数：
- 若 \(p\) 为质数，\(\varphi(p)=p-1\)；
- 若 \(p\) 为质数，\(n=p^k\)，有 \(\varphi(n)=p^k-p^{k-1}\)，即 \([1,n]\) 去掉了 \(p,2p,3p\cdots p^{k-1}p\) 共计 \(p^{k-1}\) 个数；
- 积性：若 \(a,b\) 互质，\(\varphi(ab)=\varphi(a)\varphi(b)\)，因为此时 \(a,b\) 的质因子 \(\{pi\},\{qi\}\) 均不相同，所以 \(\varphi(ab)=ab\prod\limits_{i=1}^{k}(1-\dfrac{1}{p_i})\prod\limits_{j=1}^{l}(1-\dfrac{1}{q_i})=a\prod\limits_{i=1}^{k}(1-\dfrac{1}{p_i})\times b\prod\limits_{j=1}^{l}(1-\dfrac{1}{q_i})=\varphi(a)\varphi(b)\)；
- 不完全积性：若 \(p\) 为质数，\(n\) 为 \(p\) 的倍数，则 \(n\) 与 \(np\) 的质因数种类上完全相同，有 \(\varphi(np)=np\prod\limits_{i=1}^{k}(1-\dfrac{1}{p_i})=n\prod\limits_{i=1}^{k}(1-\dfrac{1}{p_i})\times p=\varphi(n)\times p\)；
- 若 \(n\) 为奇数，则 \(\varphi(2n)=\varphi(n)\)，由方法 1,3 可推得。
结合方法 1,3,4，我们可以用线性筛的方法 \(O(n)\) 的计算 \(\varphi(i)\)，实现如下：
for (int i = 2; i <= n; i++) {
if (!isNotPrime[i]) {
primes.push_back(i);
phi[i] = i - 1; // 方法 1
}
for (int j = 0; j < primes.size() && i * primes[j] > n; j++) {
isNotPrime[i * primes[j]] = true;
if (i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j]; // 方法 4
break; // 线性筛原理：只让合数被「最小」质因数筛掉
}
phi[i * primes[j]] = phi[i] * phi[primes[j]]; // 方法 3
}
}