扩展欧几里得

一次不定方程

设整数$k \geq 2$,$c,a_1…a_k$是整数,且$a_1…a_k$都不等于零,以及$x_1…x_k$是整数变数,方程$$a_1x_1 + … + a_kx_k = c \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$$

称为k元一次不定方程,$a_1….a_k$称为它的系数.

(1)有解的充要条件: $gcd(a_1..a_k) | c$

二元一次方程

对于$ax + by = gcd(a,b)$

可以利用辗转相除法得到一组整数解$(x_0,y_0)$

那么对于$ax+by=c$

方程有解当且仅当$gcd(a,b) | c$

解为
$$\begin{cases}
x = x_{0} \times \frac{c}{gcd(a,b)} + \frac{b}{gcd(a,b)}\times t\\
{y = y_{0} \times \frac{c}{gcd(a,b)} - \frac{a}{gcd(a,b)}\times t}
\end{cases}$$

$t = 0,\pm1,\pm2….$


47x - 30y = 1与47x + 30y = 1之间有没有差别呢?

其实是没有的,实际手算过程是是不考虑负号的,最后结束的时候才会考虑。所以在
传递参数的时候只要传递47和30即可(不能传递47和-30!!),然后再去直接改变x和y的符号.

手算模拟:

47 = 30*1 + 17

30 = 17*1 + 13

17 = 13*1 + 4

13 = 4*3 + 1

4 = 4*1


17 = 47 - 30*1

13 = 30 - 17*1

4 = 17 - 13*1

1 = 13 - 4*3


1 = 13 - (17 - 131)3

= 47(-7) + 3011


x = -7 y = 11

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// ax + by = gcd(a,b)
// return d = gcd(a,b)
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
if (a == 0 && b == 0) return -1; // 无最大公因数
ll d = a;
if (b)
d = ex_gcd(b, a % b, y, x), y -= x * (a / b);
else
x = 1, y = 0;
return d;
}

// X = x + dx * t, Y = y - dy * t
// x是最小非负整数解
bool solve(ll a, ll b, ll c, ll &x, ll &y, ll &dx, ll &dy) {
ll x0, y0, d;
d = ex_gcd(a, b, x, y);
if (d == -1 || c % d) return false; //无解
dx = b / d, dy = a / d;
x = x0 * c / d;
x = (x % dx + dx) % dx;
y = (c - a * x) / b;
return true;
}