试出 3 的逆元
C++ 没有 Python 那种 pow(3, -1, 7)，先用最笨的办法挨个试： #include <array> #include <iostream> #include <string> #inc
exgcd 求的是什么
第 1 步：递归：(30, 12) 第 2 步：递归：(12, 6) 第 3 步：递归：(6, 0) 第 4 步：b 为 0：x=1，y=0 第 5 步：回代：x=下一层 y，y=… 第 6 步：回代：x=下一层 y，y=… 第 7 步：3
exgcd 的递归边界
exgcd 递归到 b == 0 时 x = 1，y =【0】。 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x、y；inv_ex(a, p) 用它求逆元。
exgcd 能顺带求什么
用 exgcd 可以直接求出【0】。 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x、y；inv_ex(a, p) 用它求逆元。
裴蜀定理
方程 a·x + b·y = c 有整数解，当且仅当【0】。 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x、y；inv_ex(a, p) 用它求逆元。
exgcd 求出的 gcd
运行下面这段程序： 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x、y；inv_ex(a, p) 用它求逆元。 #include <array> #in
补全：递归边界
补全 exgcd 的递归边界：b == 0 时 x=1、y=0。补全后输出 exgcd(30, 12) 求出的 x。 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x
补全：系数回代
补全 exgcd 的回代：y = x1 - (a / b)·y1。补全后输出 30·x + 12·y，应该等于 gcd。 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组
补全：逆元转成非负
补全 inv_ex：exgcd 得到的 x 可能是负数，要转成 0..p-1。补全后输出 3 关于 7 的逆元。 本节模型：exgcd(a, b, x, y) 返回 gcd，并通过引用参数带回 a·x + b·y = gcd 的一组 x、y
费马求逆元的前提
第 1 步：算 3 的 1～6 次方模 7 第 2 步：3 的 1 次方模 7 第 3 步：3 的 2 次方模 7 第 4 步：3 的 3 次方模 7 第 5 步：3 的 4 次方模 7 第 6 步：3 的 5 次方模 7 第 7 步：3