[学习笔记 #3] 扩展欧几里得算法（exgcd）
由于笔者太菜，本文中术语使用可能有误。
用来求二元一次不定方程的整数解。
（这个方程有整数解的[充要条件]（？）是 \(\gcd ( a, b ) | c\)。）
我们只需要求出方程 \(a x + b y = \gcd ( a, b )\) 的解，再同乘一个 \(\frac { c } { \gcd ( a , b ) }\) 得到原方程的解。
现在我们只讨论 \(a x + b y = \gcd ( a, b )\)。
为了求得一组整数解，我们考虑围绕一个不变的 \(\gcd ( a, b )\) 去改变 \(a, b\)，不断推出是原 \(a, b\) 时的解。
这使我们联想到求 \(\gcd\) 的过程。于是我们假设已经求出了 \(b, a \bmod b\) 时的解，考虑由它求出 \(a, b\) 时的解。
于是 \(x = y', y = x' - \lfloor \frac a b \rfloor y'\)（应该要用大括号括起来，但我不会写，先写成这样吧）是 \(a, b\) 时的[一组解]（？？？）。
考虑边界是什么。当 \(b = 0\) 时，方程是 \(a x = a\)，于是有 \(x = 1\)；此时直接令 \(y = 0\) 即可。
于是可以写出如下代码（在求 gcd 的过程中添加了一些东西）来求出 \(a x + b y = \gcd ( a, b )\) 的[一组解]（？）：
// 咕咕咕
记得写怎么用 exgcd 证上面那个结论。
记得写通解。
记得写用不等式来求出解的范围（求通解式子里的那个 \(k\) 的范围）。
当模数不是质数时，不能用费马小定理求乘法逆元，但如果满足模数与一个数互质，就可以用 exgcd 来求它的乘法逆元。
具体地，
\(k\) 是整数。
如果是 \(> 0\) 就要把向上取整改成向下取整再 \(+ 1\)，把向下取整改成向上取整再 \(- 1\)。
2024.10.25