ex_gcd这个东西从搞OI开始到现在好像就从来没有彻底搞清楚过，一直是迷迷糊糊背的代码，平均每几个月就要忘一次

希望这一次搞了之后以后都能想清楚了吧

Ex_Gcd

注：为了方便，以下均用 代替

辗转相除法

gcd(a,b)=gcd(b,a mod b) \gcd(a, b) = \gcd(b, a~\mathrm{mod}~b)

感性理解：gcd(a,b)=gcd(b,a−b)=gcd(b,a−2b)=⋯=gcd(b,a mod b)\gcd(a, b) = \gcd(b, a - b) = \gcd(b, a - 2b) = \cdots = \gcd(b, a~\mathrm{mod}~b)

求任意一组特解

给出 、 ，求 的解

由辗转相除法 ，易知

ax+by=g=bx′+(a mod b)y′ ax + by = g = bx' + (a~\mathrm{mod}~b)y'

那么

ax+by=ay′+b(x′−⌊ab⌋y′) ax + by = ay' + b(x' - \lfloor\frac{a}{b}\rfloor y')

于是

{x=y′y=x′−⌊ab⌋y′ \begin{cases} x = y'\\ y = x' - \lfloor\frac{a}{b}\rfloor y' \end{cases}

递归求解即可，每次回溯的时候更新 ，这样就能求出一组特解

解系扩展

这一部分一直没搞清楚

假设x0,x1,y0,y1x_0, x_1, y_0, y_1均为合法解，则

a(x0−x1)+b(y0−y1)=0 a(x_0 - x_1) + b(y_0 - y_1) = 0

于是

(ag)(x0−x1)=(bg)(y0−y1) (\frac{a}{g})(x_0 - x_1) = (\frac{b}{g})(y_0 - y_1)

因为gcd(ag,bg)=1\gcd(\frac{a}{g}, \frac{b}{g}) = 1，所以x0−x1x_0 - x_1是bg\frac{b}{g}的倍数。也就是说，任意两个解x0,x1x_0, x_1都满足它们的差是bg\frac{b}{g}的倍数。yy的部分同理

因此方程的通解x,yx, y可以通过任意一组特解x0,y0x_0, y_0表示为

{x=x0+(bg)⋅ky=y0−(ag)⋅k , k∈R \begin{cases} x = x_0 + (\frac{b}{g})\cdot k\\\\ y = y_0 - (\frac{a}{g})\cdot k \end{cases} ~, ~k\in R

因此，在求最小非负整数解时，需要 ，而非 ！！！

也就是说，在求最小非负整数解时，直接a /= g, b /= g，转化成求(ag)x+(bg)y=1(\frac{a}{g})x + (\frac{b}{g})y = 1的解，最后加bb模bb即可，不需要考虑其他问题了

或者说，在用ex_gcd求解最小非负整数解时，需要保证gcd(a,b)=1\gcd(a, b) = 1，然后就能直接模bb加bb了

Ex_Gcd求解不定方程

求解ax+by=cax+by=c的最小非负整数解

首先，cc必须为gg的倍数，若不是gg的倍数则无解

c=ax+byc = ax + by，而ax+byax + by显然为gg的倍数

求这个东西有两个本质相同的做法，以前一直没搞清：

Sol 1

ax+by=c⇔  (ag)x +(bg)y =(cg)⇒  (ag)x′+(bg)y′=1 \begin{aligned} ax + by &= c \\ \Leftrightarrow ~~(\frac{a}{g})x~ + (\frac{b}{g})y~ &= (\frac{c}{g})\\ \Rightarrow ~~(\frac{a}{g})x' + (\frac{b}{g})y' &= 1\\ \end{aligned}

利用ex_gcd解出x′x'的最小非负整数解，那么x=x′×(cg)x = x' \times (\frac{c}{g})

Sol2

ax+by=c⇒         ax′ +by′ =g⇔  (ag)x′+(bg)y′=1 \begin{aligned} ax + by &= c \\ \Rightarrow ~~~~~~~~~ax'~ + by'~ &= g\\ \Leftrightarrow ~~(\frac{a}{g})x' + (\frac{b}{g})y' &= 1\\ \end{aligned}

利用ex_gcd解出x′x'的最小非负整数解，那么x=x′×(cg)x = x' \times (\frac{c}{g})

写出来就发现这两个做法本质相同

以前没搞清楚就是因为不知道解系扩展的时候需要保证gcd(a,b)=1\gcd(a, b) = 1，或者说乘的是(bg)(\frac{b}{g})。就导致了想不清楚应该在什么时候加模取模，不知道应该加模取模哪个数，到底是bb还是(bg)(\frac{b}{g})

实际写代码的时候一般写第一种方法，拿到方程之后就把a,b,ca, b, c除gg变成新的a,b,ca, b, c，然后进行ex_gcd，假设求出来的解为x′x'，那么原方程最小非负整数解x=(x′×(cg)+b) mod bx = (x' \times (\frac{c}{g}) + b)~\mathrm{mod}~b即可。因为现在已经保证了gcd(a,b)=1\gcd(a, b) = 1

如果原来的方程还要用的话最后还是乘回去吧。。。