扩展欧几里得算法（Exgcd）

裴蜀定理

对于任意一组整数 \(a,b\)，存在一组整数 \(x,y\)，满足 \(ax+by=\gcd(a,b)\)。

Proof：

考虑数学归纳法。

当 \(b=0\) 时，由于 \(\gcd(a,0)=a\)，则对于 \(ax+0y=a\) 这个不定方程，\(x=1\)，\(y\) 取任意整数。

假设存在一组整数 \(x,y\)，满足 $bx+(a\bmod b)y=\gcd(b,a\bmod b)=\gcd(a,b) $。

那么接下来证明也存在一组整数 \(x',y'\) 满足 \(ax'+by'=\gcd(a,b)\)。

\[\begin{aligned}

bx+(a\bmod b)y &= bx+(a-b\lfloor\dfrac{a}{b}\rfloor)y\\

&= bx+ay-b\lfloor\dfrac{a}{b}\rfloor y\\

&= ay+b(x-\lfloor\dfrac{a}{b}\rfloor y)

\end{aligned}

\]

当 \(x'=y,y'=x-\lfloor\dfrac{a}{b}\rfloor y\) 时满足条件。

那么利用辗转相除法进行递归，总能递归到 \(b=0\) 的情况。命题得证。

Exgcd

求关于 \(x,y\) 的方程 \(ax+by=c\) 的整数解。

设 \(d=\gcd(a,b)\)，方程有整数解的充要条件是 \(d\mid c\)。

Proof：

设 \(a=k_1d,b=k_2d\)，则有 \(k_1dx+k_2dy=c \Rightarrow k_1x+k_2y=\dfrac{c}{d}\)。

先证必要性： 由于 \(\dfrac{c}{d}\) 必须为整数，则 \(d \mid c\)。

再证充分性：上式中，\(k_1\perp k_2\)，则方程 \(k_1x'+k_2y'=1\) 一定有整数解。由于 \(\dfrac{c}{d} \in\mathbb{Z}\)，那么原方程也一定有整数解。

先将方程化简，两边同除以 \(d\)。此时 \(a,b\) 互质。

为了方便表述，下面提到的方程都是化简后的方程。

那么我们可以先利用裴蜀定理求出 \(ax'+by'=1\) 的一组特解 \(x',y'\)，从而求出原方程的一组特解 \(x_0=cx’,y_0=cy'\)。

考虑如何求出通解。

让 \(x\) 加上一个数，那么 \(y\) 就要减去一个数。设这两个数为 \(\Delta_x,\Delta_y\)，则有：

\[\begin{aligned}

a(x+\Delta_x)+b(y-\Delta_y) &= c\\

ax+a\Delta_x+by-b\Delta_y &= c\\

a\Delta_x-b\Delta_y&=0\\

a\Delta_x &= b\Delta_y \\

\dfrac{a}{b} &= \dfrac{\Delta_y}{\Delta_x}

\end{aligned}

\]

由于 \(a,b\) 互质，则 \(\dfrac{a}{b}\) 为最简整数比，则有 \(a \mid \Delta_y\) 且 \(\ b\mid \Delta_x\)。

由于 \(\Delta_x,\Delta_y \in \mathbb{Z}\)，则 \(\Delta_x\) 最小取到 \(b\)，\(\Delta_y\) 最小取到 \(a\)。

通解即为：

\[\begin{cases}

x=x_0+kb\\

y=y_0+ka\\

\end{cases}

(k\in \mathbb{Z})

\]

代回原方程，可以消掉 \(kb,ka\)。

接下来考虑，当存在正整数解时，如何求出最小正整数解与正整数解的个数。

对 \(x\) 的通解进行变形，求 \(x\) 的最小正整数解 \(x_1\)：

\[\begin{aligned}

x_1 \bmod b &= (x_0+kb) \bmod b\\

x_1 \bmod b &= x_0 \bmod b\\

x_1&=(((x_0-1) \bmod b)+b)\bmod b+1

\end{aligned}

\]

先减一是为了避免 $x_0 \bmod a $ 一开始就为 \(0\) 的情况，从而保证 \(x_1>0\)。

易得，当 \(x\) 增大时，\(y\) 减小。当 \(x\) 取 \(x_1\) 时，\(y\) 取到最大正整数解 \(y_2\)。

同理，求出 \(y\) 的最小正整数解 \(y_1\)，当 \(y\) 取 \(y_1\) 时，\(x\) 取到最大正整数解 \(x_2\)。

由通解公式可得，\(x\) 每两个整数解之间相差 \(b\)，\(y\) 每两个整数解之间相差 \(a\)。

正整数解的个数即为 \(\dfrac{x_2-x_1}{b}+1\) 或 \(\dfrac{y_2-y_1}{a}+1\)。

Ex.1 【模板】二元一次不定方程 (exgcd)

根据上面的分析，套用公式即可。

<code>ll T,A,B,C,x,y,d,x1,x2,y1,y2,cnt;

ll GetX(ll Y){return (C-B*Y)/A;}

ll GetY(ll X){return (C-A*X)/B;}

ll Exgcd(ll a,ll b,ll &x,ll &y){

if(b==0) return x=1,y=0,a;

ll res=Exgcd(b,a%b,x,y);

ll z=x;

x=y;

y=z-(a/b)*y;

return res;

}

void Solve(){

read(A),read(B),read(C);

d=Exgcd(A,B,x,y);

if(C%d) return puts("-1"),void();

A/=d,B/=d,C/=d;

x*=C,y*=C;

x1=((x-1)%B+B)%B+1;

y2=GetY(x1);

y1=((y-1)%A+A)%A+1;

x2=GetX(y1);

cnt=(x2-x1)/B+1;

if(y2<=0) printf("%lld %lld\n",x1,y1);

else printf("%lld %lld %lld %lld %lld\n",cnt,x1,y1,x2,y2);

}

Ex.2 [NOIP2012 提高组] 同余方程

对式子进行变形：

\[\begin{aligned}

ax &\equiv 1 \pmod{b}\\

ax+by &= 1

\end{aligned}

\]

利用 Exgcd 求解即可。

这是非常常用的变形技巧，也是当 \(a,b\) 互质但 \(b\) 不是质数时求逆元的方法。

Ex.3 青蛙的约会

设跳跃 \(k\) 次后两青蛙相遇，则可列出方程：

\[\begin{aligned}

x+kn &\equiv y+km &\pmod{L}\\

(x-y)+k(n-m) &\equiv 0 &\pmod{L}\\

(x-y)+k(n-m) &= pL\\

k(n-m)-pL&=y-x\\

kS-pL&=C

\end{aligned}

\]

其中 \(S,L,C\) 为常数。

把 \(k,p\) 看作未知数，利用 Exgcd 求 \(k\) 的最小正整数解即可。