拓展欧几里得

我们先回忆一下朴素的欧几里得算法（辗转相除法）

$gcd(a,b)=gcd(b,a%b)$

1

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

而拓展欧几里得（exgcd）常用来求$ax+by=gcd(a,b)$的一组解。

ax+by=gcd（a,b)

设$x_1,y_1$满足原方程$ax_1+by_1=gcd(a,b)$

根据欧几里得算法不妨构造这样一个方程：

$x_2,y_2$满足$bx_2+(a;mod;b)y_2=gcd(b,a;mod;b)$

所以可得 $ax_1+by_1=bx_2+(a;mod;b)y_2$

由于$a;mod;b=a-(\lfloor\frac{a}{b}\rfloor\times b)$

代入化简，得$ax_1+by_1=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)$

所以可得$x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$

我们知道欧几里得算法不停辗转相除下去，最终会得到a=gcd（a，b），b=0。

因此我们可以根据这个性质不停的构造如上的方程，最后会得到

$gcd(a,b)x+0\times y=gcd(gcd(a,b),0)$

显然此时x=1，y=0可作为方程的一组解，那么只需将这组解往回迭代上去就可以求得原方程的解了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = exgcd(b, a % b, x, y);
  ll t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
//exgcd返回的值为gcd（a，b）

ax+by=c

通过上面的方程求解我们不难得到对一个更加普通的不定方程$ax+by=c$的一组解。

设$x_0,y_0$满足$ax_0+by_0=gcd(a,b)$

将$ax_0+by_0=gcd(a,b)$两边同除gcd（a，b）再同乘c

可得$a\frac{cx_0}{gcd(a,b)}+b\frac{cy_0}{gcd(a,b)}=c$

所以，$x=\frac{c}{gcd(a,b)}x_0,y=\frac{c}{gcd(a,b)}y_0$

同时，我们发现$ax+by=c$存在整数解的充要条件为$c%gcd（a,b）=0$；

那么，如果题目要求我们求出x的最小可行解呢？

可令$t=b/gcd(a,b)$，最小的$x=(x;mod;t+t)mod;t$

我们为了让x最小，那么y要尽可能的大，我们可以将x尽可能分成每份为t，因为$t\times a$可以被b整除，所以这些从x里分出来的可给y，那么剩下的x就最小了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = exgcd(b, a % b, x, y);
  ll t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
//ax+by=c,ax%b=c%b;
ll lieu(ll a,ll b,ll c,ll &x,ll &y)
{
    ll d=exgcd(a,b,x,y);
    if(c%d!=0)return 0;
    ll k=c/d;
    x*=k;
    y*=k;
    ll t=b/d;
    x=(x%t+t)%t;
    y=(c-a*x)/b;
    return x;
}

线性同余方程

$ax\equiv c(mod;b)$

将上面的$ax+by=c$两边同时mod b，我们发现它就转化为$ax\equiv c(mod;b)$这个式子。

也就是说其实$ax+by=c$与 $ax\equiv c(mod;b)$是等价的，那么我们其实已经知道如何求得线性同余方程的解了。

同时我们也知道线性同余方程有解的充要条件为$c%gcd（a,b）=0$

拓展欧几里得