裴蜀定理
方程 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
exgcd 逆元好在哪
相比费马小定理，exgcd 求逆元的好处是【0】。 本节模型：inv(a, p) 用费马小定理求逆元：p 是质数时 a^(p-2) mod p。
有了逆元能做什么
模意义下有了逆元，就能做【0】。 本节模型：inv(a, p) 用费马小定理求逆元：p 是质数时 a^(p-2) mod p。
费马求 3 的逆元
运行下面这段程序： 本节模型：inv(a, p) 用费马小定理求逆元：p 是质数时 a^(p-2) mod p。 #include <array> #include <iostream> #include <s
大质数下 2 的逆元
运行下面这段程序： 本节模型：inv(a, p) 用费马小定理求逆元：p 是质数时 a^(p-2) mod p。 #include <array> #include <iostream> #include <s