专题：快速幂、模运算与乘法逆元

1. 分子分母都能取模，可”除法”怎么办？

先看清楚问题有多严重。在模 $p$ 意义下：

$$ (a+b)\bmod p,\quad (a-b)\bmod p,\quad (a\times b)\bmod p $$

这三个都能随时取模、随便拆——因为取模和加减乘是可交换的。但除法不行：

$$ \frac{10}{4}\bmod 7 \ne \frac{10\bmod 7}{4\bmod 7} = \frac{3}{4} $$

右边根本不是整数。而且 $10/4=2.5$ 本身就不是整数——“模意义下的除法”到底是什么意思，都还没定义。

答案是：模意义下没有除法，只有”乘以逆元”。 而求逆元最常用的办法要先会快速幂。所以本讲的顺序是：模运算 → 快速幂 → 逆元 → 还账。

运算	模意义下
加	$(a+b)\bmod p=((a\bmod p)+(b\bmod p))\bmod p$ ✓
减	$(a-b)\bmod p=((a\bmod p)-(b\bmod p)+p)\bmod p$ ✓ （要 `+p`，C++ 的 `%` 对负数返回负数）
乘	$(a\times b)\bmod p=((a\bmod p)\times(b\bmod p))\bmod p$ ✓
除	✗ 没有这条。要改写成 $a\times b^{-1}\bmod p$（第 4 节）

两个立刻要记住的工程细节：

减法一定要 +p。 C++ 里 (-5) % 7 == -5，不是 2。本讲所有代码里凡是有减法的地方都写成 (x % p + p) % p。
一路取模，不要”先算完再取模”。 后者早就溢出了——第 3.5 节量了溢出的确切边界。

要算 $a^{b}\bmod p$，$b$ 可以到 $10^{18}$，一个一个乘显然不行。

把 $b$ 写成二进制。比如 $b=13=1101_2=8+4+1$，那么