扩展欧几里得 Exgcd 总结

原理：

Code

int Exgcd(int a, int b, int &x, int &y) {if (!b) {x = 1, y = 0;return a;}int x1 = 0, y1 = 0;int d = Exgcd(b, a % b, x1, y1);x = y1;y = x1 - (a / b) * y1; return d;
}

套路

First

求解 \(ax + by = c\).

1. 解 \(ax + by = gcd(a, b)\)
2. beishu 定理 判断是否有解，\(\gcd(a, b) \mid c\)
3. 乘系数 \(\frac{c}{d}\)
4. 若需求最小非负整数解，a /= d, b /= d, c /= d; x = (x % b + b) % b, y = (y % a + a) % a;

Second

求解 \(ax\) 与 \(c\) 在模 \(b\) 意义下同余的方程.

等价于 \(ax + by = c\)

要点

1. 不要缺少步骤
2. 辗转相除时得到的 \(d\) 有可能为负，此时 \(ax + by\) 也为负。
3. 步骤 4 的除法操作目的是减小循环节，模操作的目的是剔除循环部分，找到最小的
4. 步骤四相当于 \(ax + by = c \to \frac{a}{d} x + \frac{b}{d} y = \frac{c}{d}\)
5. 尽量使得 \(a, b\) 为正
6. 同余式可以移项
7. 类似青蛙一题，位置可以表示为 \(vt + s\), 形式上等价于不定方程一元的通解，使用 exgcd 求，则该题求解两不定方程一元的共同解，也用 exgcd，所以可以用套娃的方式求多个不定方程一元的共同解，和共同解的共同解？

Problem

P2613 【模板】有理数取余

P1516 青蛙的约会

P5656 【模板】二元一次不定方程 (exgcd)

启示：找到 \(x\) 的最小正整数解后利用 \(ax + by = c\) 解出 对应最大 \(y\)

CF710D Two Arithmetic Progressions

题解：类似于 P2，但要求解一个区间内解的数量，解出 \(k, l\) 分别的最小非负整数解，就可以找出最小的使得 \(k, l\) 同时为非负整数的解。则通解可表示为为此解加上循环节，且循环节的倍数为正。然后解不等式算出循环节倍数的范围需要注意 \(a, b\) 可能为负。

启发：要考虑 \(a, b\) 为负情况。

CF982E Billiard

题解：反弹只是对称改变方向，不会影响之后的反弹，所以干脆不反弹。于是最后的球洞坐标可用两同余方程第一个共同解表示，又等价于反弹次数。发现真实球洞与反弹次数和初始朝向的奇偶有关，于是计算即可。细节考虑起点是否发生反弹。

启示：主要是反弹的这个模型。