快速幂

https://oi-wiki.org/math/binary-exponentiation/

计算过程：

例题列表

875. 快速幂⭐⭐⭐⭐⭐（重要！）

https://www.acwing.com/activity/content/problem/content/944/

求 a ^ b % p，时间复杂度是 $O(\log b)$

代码写法1——递归

对于递归写法比较好理解
对于求 $m^k\mathrm{mod}p$ 每次将 k 缩小到原来的一半。

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- != 0) {
            long a = sc.nextInt(), b = sc.nextInt(), p = sc.nextInt();
            System.out.println(qmi(a, b, p));
        }
    }

    static long qmi(long a, long b, long p) {
        if (b == 0) return 1;
        long res = qmi(a, b / 2, p) % p;
        if (b % 2 == 0) return res * res % p;
        else return res * res * a % p;
    }
}

代码写法2——迭代

关于迭代版的解释看一个例子比较清楚：

对于求 m ^ k % p。
我们预处理出 $m^{2^0}、m^{2^1}、m^{2^2}、m^{2^3}...$ 这里的每一项都是前一项的平方，对应代码中的 t = t * t % p

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- != 0) {
            long a = sc.nextInt(), b = sc.nextInt(), p = sc.nextInt();
            System.out.println(qmi(a, b, p));
        }
    }

    // 迭代版快速幂
    static long qmi(long a, long b, long p) {
        long res = 1 % p, t = a;
        // 把 b 看成二进制数字，哪些位置是 1 就把它乘起来就好了
        while (b != 0) {
            if ((b & 1) == 1) res = res * t % p;
            t = t * t % p;
            b >>= 1;
        }
        return res;
    }
}

递归写法 与 迭代写法的 对比

876. 快速幂求逆元🚹（需要理解逆元的概念）TODO

https://www.acwing.com/problem/content/878/

乘法逆元介绍

https://oi-wiki.org/math/number-theory/inverse/

那么什么是线性同余方程？

就是希望找到一个数 x，使得 a / b 的结果与 a * x mod m 之后结果相同。

解法代码

在这里插入代码片