扩展欧几里得（EXGCD）

基本内容

exgcd 通常用于求解形如 \(ax+by=gcd(a,b)\) 的一组整数解。

考虑有

\[ax+by=\gcd(a,b) \]

\[bx^{\prime}+(a\bmod b)y^{\prime}=\gcd(b,a\bmod b) \]

容易发现，如果我们可以用 \(x^{\prime},y^{\prime}\) 来表示 \(x,y\)。那么我们就可以一直向下递归直至 \(b=0\)，此时我们发现显然有一组解为 \(x=1,y=0\)。再回溯回去就能求出原方程的一组解。

\[bx^{\prime}+(a\bmod b)y^{\prime} \]

\[=bx^{\prime}+(a-\lfloor\frac{a}{b}\rfloor\times b)y^{\prime} \]

\[=bx^{\prime}+ay^{\prime}-\lfloor\frac{a}{b}\rfloor by^{\prime} \]

\[=ay^{\prime}+b(x^{\prime}-\lfloor\frac{a}{b}\rfloor y^{\prime}) \]

由欧几里得定理得 \(\gcd(a,b)=\gcd(b,a\bmod b)\)。

\(\therefore ay^{\prime}+b(x^{\prime}-\lfloor\frac{a}{b}\rfloor y^{\prime})=ax+by\)

因为 \(a=a,b=b\)，所以可以令 \(x\) 取 \(y^{\prime}\)，令 \(y\) 取 \(x^{\prime}-\lfloor\frac{a}{b}\rfloor y^{\prime}\).

最后依照这种类似欧几里得算法的做法进行递归，直至 \(b=0\) 时令 \(x=1,y=0\)即可。

代码如下。

void exgcd(int a, int b, int &x, int &y) {if (b == 0) {x = 1, y = 0;return;}exgcd(b, a % b, x, y);int t = x;x = y;y = t - (a / b) * y;
}

这样我们就可以的出一组解 \(x,y\).

我们发现 \(ax+by=ax+by+\frac{ab}{\gcd(a,b)}-\frac{ab}{\gcd(a,b)}=a(x+\frac{b}{\gcd(a,b)}) + b(y-\frac{a}{\gcd(a,b)})=\gcd(a,b)\).

所以可以令 \(x:=x+\frac{b}{\gcd(a,b)},y:=y-\frac{a}{\gcd(a,b)}\)，方程仍然成立（同理可以令\(x:=x-\frac{b}{\gcd(a,b)},y:=y+\frac{a}{\gcd(a,b)}\)）。

所以当我们使用上述操作得到一组解 \(x,y\) 后就可以再得到无穷多组解。

那么这无穷多组解的集合是否与原方程的整数解集相等呢？我发现不仅在网络上大部分题解/博客没有对这个问题进行证明，oi-wiki 上也没有进行证明，所以我在这里进行一下证明。

证明

(本证明思路来自 unordered)

\[ax+by=\gcd(a,b) \]

\[ax^{\prime}+by^{\prime}=gcd(a,b) \]

\[x=x^{\prime}-\frac{b}{\gcd(a,b)},y=y^{\prime}+\frac{a}{\gcd(a,b)} \]

不妨设 \(a>0,b>0\).

两式相减得 \(a(x-x^{\prime})=b(y^{\prime}-y)\).

不难发现上式等于 \(\operatorname{lcm}(a,b)\)，记为 \(S\).

假设 \(\exists x_1\in (x,x^{\prime})\cap Z\) 使得 \(\exists y_1\in (y^{\prime},y)\cap Z\) 满足 \(ax_1+by_1=\gcd(a,b)\).

则 \(a(x-x_1)=b(y-y_1)\).

不难发现上式为 \(\operatorname{lcm}(a,b)\) 的倍数且小于 \(S\)。

与题设矛盾。

故由 \((x,y)\) 得出的 \((x^{\prime},y^{\prime})\) 能遍历原方程的整个整数解集。