扩展欧几里得

一次不定方程

设整数$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$

设二元一次不定方程$$a_1x_1 + a_2x_2 = c\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$$

有解,$x_{1,0},x_{2,0}$是它的一组解,那么它的所有解为

$$\begin{cases}
x_1 = x_{1,0} + \frac{a_2}{(a_1,a_2)}\times t\\
{x_2 = x_{2,0} - \frac{a_1}{(a_1,a_2)}\times t}
\end{cases}$$

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

其中$(a_1,a_2)$ 表示二者的最大公约数

$$\begin{cases}
a_{11}x_1&+&a_{12}x_2&+&\cdots&+a_{1n}x_n&=&b_1 \\
&&&&\vdots\\
a_{n1}x_1&+&a_{n2}x_2&+&\cdots&+a_{nn}x_n&=&b_n&
\end{cases}$$

扩展欧几里得算法

对于$ax + by = c$

exgcd会先算$ax + by = 1$

得到的一组解$x_1,y_1$要再乘$c$才是最后的答案。


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

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

手算模拟:

47 = 30*1 + 17

30 = 17*1 + 13

17 = 13*1 + 4

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
25
26
27
28
// ax + by = 1
ll ex_gcd(ll a,ll b,ll &x,ll &y){
if((b == 0) && (a == 0)) return -1; //无最大公因数
if(b == 0){
x = 1;
y = 0;
return a;
}
else{
ll d = ex_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
}

int main(){
ll a,b,c; // ax + by = c;
cin >> a >> b >> c;
ll x,y;
ll d = ex_gcd(a,b,x,y); // 返回gcd(a,b)
if(c % d != 0) cout << "无解" << endl;
else{
// x = (x % (b/d) + b/d) % (b/d) //取最大非负整数
// y = (1 - a*x) / b;
x *= c;
y *= c;
}
}
Thank you for your support!