【exgcd】不定方程整数通解
拓展欧几里得算法
设
{ax1+by1=gcd(a,b)bx2+(amodb)y2=gcd(b,amodb)\left\{\begin{matrix} a x_1 + b y_1 = gcd ( a , b ) \\ b x_2 + ( a m o d b ) y_2 = gcd ( b , a m o d b ) \end{matrix}\right.{ax1+by1=gcd(a,b)bx2+(a mod b)y2=gcd(b,a mod b)由欧几里得定理可知：gcd(a,b)=gcd(b,amodb)gcd ( a , b ) = gcd ( b , a m o d b )gcd(a,b)=gcd(b,a mod b)
所以 ax1+by1=bx2+(amodb)y2a x_1 + b y_1 = b x_2 + ( a m o d b ) y_2ax1+by1=bx2+(a mod b)y2
又因为 amodb=a−(⌊ab⌋×b)a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)amodb=a−(⌊ba⌋×b)
所以有 ax1+by1=bx2+(a−(⌊ab⌋×b))y2ax_1+by_1=bx_2+(a-(\lfloor\frac{a}{b}\rfloor\times b))y_2ax1+by1=bx2+(a−(⌊ba⌋×b))y2化简得
ax1+by1=ay2+bx2−⌊ab⌋×by2=ay2+b(x2−⌊ab⌋y2)ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)ax1+by1=ay2+bx2−⌊ba⌋×by2=ay2+b(x2−⌊ba⌋y2)
因为 a=a,b=ba = a , b = ba=a,b=b，所以 x1=y2,y1=x2−⌊ab⌋y2x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2x1=y2,y1=x2−⌊ba⌋y2
因为方程 ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b) 在 a=a,b=0a=a,b=0a=a,b=0时，显然有解 x=1,y=0x=1,y=0x=1,y=0，我们可以利用欧几里得算法的 a=b,b=a%ba=b,b=a\%ba=b,b=a%b 的递归和 a=a,b=0a=a,b=0a=a,b=0 的递归边界，通过上面推导出的结论将x=1,y=0x=1,y=0x=1,y=0的解不断还原，来实现求得原方程的一组特殊解。
代码如下：
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(b==0){x=1,y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
//以上删改自大佬算法博客
求不定方程整数通解
对于不定方程
ax+by=cax+by=cax+by=c
根据裴蜀定理，显然有 gcd(a,b)∣c\gcd(a,b)|cgcd(a,b)∣c
我们已知 exgcdexgcdexgcd 可以求出不定方程
ax+by=gcd(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b)
的一组整数特解，我们记为 x0x_0x0 与 y0y_0y0
则有
ax0+by0=gcd(a,b)ax_0+by_0=\gcd(a,b)ax0+by0=gcd(a,b)ax0cgcd(a,b)+by0cgcd(a,b)=ca\frac{x_0c}{\gcd(a,b)}+b\frac{y_0c}{\gcd(a,b)}=cagcd(a,b)x0c+bgcd(a,b)y0c=c
故我们已经找到了原方程的一组整数特解，记为 x1x_1x1 和 y1y_1y1
x1=x0cgcd(a,b),y1=y0cgcd(a,b)x_1=\frac{x_0c}{\gcd(a,b)}, y_1=\frac{y_0c}{\gcd(a,b)}x1=gcd(a,b)x0c,y1=gcd(a,b)y0c
那么我们考虑构造原方程整数通解形式。
若当前已知方程一组解为x1,y1x_1,y_1x1,y1，我们设 x=x1+ix=x_1+ix=x1+i，y=y1−j(其中k∈Z,i,j∈N∗)y=y_1-j\ \ (其中k\in Z,i,j\in N^*)y=y1−j (其中k∈Z,i,j∈N∗)，那么有
{ax1+by1=ca(x1+i)+b(y1−j)=c→i=b∗ja,j=a∗ib\left\{\begin{matrix} ax_1+by_1=c \\ a(x_1+i)+b(y_1−j)=c \end{matrix}\right. →i= \frac{b∗j}{a},j= \frac {a*i}{b} {ax1+by1=ca(x1+i)+b(y1−j)=c→i=ab∗j,j=ba∗i
我们希望i,ji,ji,j尽可能小，以便能通过它们从一组特解出发，递推出方程的所有整数解。
由于iii为正整数，因此有a∣(b∗j),b∣(b∗j)a|(b*j),b|(b*j)a∣(b∗j),b∣(b∗j)。若要使jjj尽可能小，则b∗jb*jb∗j要尽可能小，而显然其最小为lcm(a,b)=a∗bgcd(a,b)lcm(a,b)=\frac{a*b}{gcd(a,b)}lcm(a,b)=gcd(a,b)a∗b，那么jjj最小为agcd(a,b)\frac{a}{gcd(a,b)}gcd(a,b)a。
同理可得，iii最小为bgcd(a,b)\frac{b}{gcd(a,b)}gcd(a,b)b。
在已知i,ji,ji,j后，我们就可以将求出的x,yx,yx,y再次带入x1,y1x_1,y_1x1,y1中，从而递推出该方程的所有整数解。
由此得出原方程整数通解的形式
x=x1+k∗bgcd(a,b),y=y1−k∗agcd(a,b)x=x_1+k*\frac{b}{gcd(a,b)},y=y_1-k*\frac{a}{gcd(a,b)}x=x1+k∗gcd(a,b)b,y=y1−k∗gcd(a,b)a
其中，kkk 属于任意整数
而且，随着 xxx 增大 yyy 减小 （它们的和一定）
而且，kkk 越大，xxx 越大，yyy 越小，反之亦然。
//以上部分删改自大佬题解
最小(最大)正整数解及正整数解数
(正整数解的定义为x,yx,yx,y均为正整数的一组解)
x=x1+k∗bgcd(a,b),y=y1−k∗agcd(a,b)(k∈Z)x=x_1+k*\frac{b}{gcd(a,b)},y=y_1-k*\frac{a}{gcd(a,b)}\ \ (k\in Z)x=x1+k∗gcd(a,b)b,y=y1−k∗gcd(a,b)a (k∈Z)
记tx=bgcd(a,b)t_x=\frac{b}{gcd(a,b)}tx=gcd(a,b)b，设xxx的最小正整数解为xmin=x1+kx∗txx_{min}=x_1+k_x*t_xxmin=x1+kx∗tx，则有x1+kx∗tx≥1x_1+k_x*t_x\ge1x1+kx∗tx≥1，得到kx≥⌈1−x1tx⌉k_x\ge\left \lceil \frac{1-x_1}{t_x} \right \rceilkx≥⌈tx1−x1⌉
同理有ky≥⌈1−y1ty⌉k_y\ge\left \lceil \frac{1-y_1}{t_y} \right \rceilky≥⌈ty1−y1⌉，当 kkk 等于 kx,kyk_x,k_ykx,ky 时，x,yx,yx,y取得最小正整数解。
当x=xminx=x_{min}x=xmin时，将xminx_{min}xmin代入方程，解得的yyy即为ymaxy_{max}ymax。同理可得xmaxx_{max}xmax。
正整数解的个数显然等于(xmax−xmin)/bgcd(a,b)+1(x_{max}-x_{min})/\frac{b}{gcd(a,b)}+1(xmax−xmin)/gcd(a,b)b+1（同理可用yyy得）。