快速幂

快速幂算法可以在 $O (\log k)$ 时间内求出 $a^{k} \mod p$ 的结果。其中 $a, p, k \leq 10^{9}$ 。暴力做法至少要循环 $k$ 次，时间复杂度为 $O (k)$ 的。

反复平方法：

预处理以下值： $a^{2^{i}} \mod p$ ，其中 $i = 0, 1, \dots, \log k$
而根据 $k$ 的二进制表示，例如 $(11)_{10} = (1011)_{2}$ ，是 1 的位就加上即可
这里还有模的积性：若 $a \equiv a_{1} (\mod p), b \equiv b_{1} (\mod p)$ ，那么 $a b \equiv a_{1} b_{1} (\mod p)$ （代入证明一下即可）

核心代码：

cpp

int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) {
            res = (LL)res * a % p;
        }

        k >>= 1;

        a = (LL)a * a % p;
    }
}

if (k & 1) 当末位数字是 1 时，乘以这个时候的 $a^{2^{i}}$ （模了 $p$ 之后的值）
每次 k 都要右移一位
每次 a 更新，其实就是自身 反复平方

其实：

前面的是：res = (LL)res * (a % p);
后面的是：a = (LL)(a * a) % p;

快速幂求逆元

逆元定义：若整数 $b, m$ 互质，且对于任意整数 $a$ ，如果满足 $b | a$ ，那么存在一个整数 $x$ ，使得：

\frac{a}{b} \equiv a \times x (\mod m)

同时称 $x$ 为 $b$ 模 $m$ 的 乘法逆元，记为 $b^{- 1} (\mod m)$ 。整数 $b$ 存在乘法逆元的充要条件是 $b, m$ 互质。注意，这里的 $x$ 只与 $b, m$ 有关，与 $a$ 怎么取无关。

证明：对上面式子两边同时乘以 $b$ ，因此有：

a \equiv a b b^{- 1} (\mod m)

由于乘法逆元与 $a$ 怎么取无关，不妨设 $(a, m) = 1$ （注意到，如果取其他的 $a$ 使得二者不互质，那么在互质条件下得到的后续条件也能使得这样的 $a$ 满足上述等式）。当 $(a, m) = 1$ 后，两边同时删除 $a$ ，得到：

b b^{- 1} \equiv 1 (\mod m)

该条件对于不互质的 $a$ 也有上上式子成立。属于是 必要条件。

所谓的求逆元问题就是找到满足 $b x \equiv 1 (\mod m)$ 的 $x$ 。

费马小定理

对于正整数 $a$ 和素数 $p$ ，有：

a^{p} \equiv a (\mod p)

我们先证明一个引理：若 $a_{1}, a_{2}, \dots, a_{m}$ 是 $m$ 的一个完全剩余系，那么对于和它互质的整数 $b$ 而言， $b a_{1}, b a_{2}, \dots, b a_{m}$ 也是 $m$ 的一个完全剩余系。证明如下：只需要证明任意两个 $b a_{j}$ 模 $m$ 不同余即可：

b a_{i} \equiv b a_{j} (\mod m) \Rightarrow a_{i} \equiv a_{j} (\mod m)

这下直接矛盾。因此引理得证。而 $1, 2, \dots, p - 1$ 正是素数 $p$ 的一个完全剩余系，而对于不是 $p$ 倍数的 $a$ 而言显然有 $(a, p) = 1$ （如果 $a$ 是 $p$ 的倍数，那么费马小定理原等式显然成立），因此新的 $a, 2 a, \dots, (p - 1) a$ 也是素数 $p$ 的一个完全剩余系。因此将它们乘起来：

1 \times 2 \times \dots \times (p - 1) \equiv [a \times 2 a \times \dots \times (p - 1) a] (\mod p)

由于 $(p - 1)!$ 显然和 $p$ 互素，因此有：

a^{p - 1} \equiv 1 (\mod p)

这正是费马小定理的一个推论，前提是 $(a, p) = 1$ ，如果扩展到任意正整数，那么就是费马小定理的原式。

回到原题，对于 $(b, p) = 1$ ，那么 $b$ 的逆元就是 $b^{p - 2}$ 。

AC876. 快速幂求逆元

快速幂 ​

快速幂求逆元 ​

费马小定理 ​

快速幂

快速幂求逆元

费马小定理