最大公约数由
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
%
b
)
gcd(a,b) = gcd(b,a\%b)
gcd(a,b)=gcd(b,a%b) 辗转相除法得到,
贝祖定理
存在整数a,b ,那么一定存在整数x,y,使得
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax+by = gcd(a,b)
ax+by=gcd(a,b)
可以判断
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax + by = gcd(a,b)
ax+by=gcd(a,b)是否有解,或者
a
x
+
b
y
=
m
ax + by = m
ax+by=m 且
m
=
k
∗
g
c
d
(
a
,
b
)
m = k * gcd(a,b)
m=k∗gcd(a,b)通过求gcd时 推x,y首先是一组特解x = 1 y = 0
假设在辗转求gcd时满足一组
b
∗
x
+
(
a
%
b
)
∗
y
b*x+(a\%b)*y
b∗x+(a%b)∗y (注意到此时a=b b=a%b,后面会解释)
(在
c
+
+
c++
c++中 a%b = a-(a/b)*b)
带入上式中
b
∗
x
+
{
a
−
(
a
/
b
)
∗
b
}
∗
y
b*x+\{a-(a/b)*b\}*y
b∗x+{a−(a/b)∗b}∗y ->
b
∗
x
+
a
∗
y
−
(
a
/
b
)
∗
b
∗
y
b*x+a*y-(a/b)*b*y
b∗x+a∗y−(a/b)∗b∗y->
a
∗
y
+
b
∗
{
x
−
(
a
/
b
)
∗
y
}
a*y+b*\{x-(a/b)*y\}
a∗y+b∗{x−(a/b)∗y}. 将此式对比原式
a
∗
x
+
b
∗
y
=
g
c
d
(
a
,
b
)
a*x+b*y = gcd(a,b)
a∗x+b∗y=gcd(a,b)
得到了x,y的递推方程
x
=
y
x = y
x=y
y
=
{
x
−
(
a
/
b
)
∗
y
}
y = \{x-(a/b)*y\}
y={x−(a/b)∗y}代码表示就为
int temp = y;
y = x - (a/b) * y;
x = temp;
还要注意到带入的式子
b
∗
x
+
(
a
%
b
)
∗
y
b*x+(a\%b)*y
b∗x+(a%b)∗y (此时a = b b = a%b)所以我们在递推x,y时,当前一步求的x,y是在下一步中得到,因为下一步a == b , b == a % b,所以写在递归回溯的地方
#include <iostream>
using namespace std;
int exgcd(int a,int b,int& x,int& y) {//扩展欧几里得算法
if(b == 0) {
x = 1;
y = 0;
return a; //到达递归边界开始向上一层返回
}
int r = exgcd(b,a%b,x,y); // 在满足 ax + by -> bx + (a%b)y -> bx+(a-a/b*b)y -> ay + b(x - a/by)
int temp = y; //保存一下 y,
y = x - (a/b) * y;
x = temp;
return r; // 在求gcd的时候将 x,y 也通过递推求出
}
int gcd(int a,int b) {
while (b != 0) {
int temp = a;
a = b;
b = temp % b;
}
// cout << "a " << a << "b " << b << endl;
return a;
}
int main() {
while (1) {
int a,b;
int x = 0,y = 0;
cin >> a >> b;
cout << "gcd: " << gcd(a,b) << endl;
exgcd(a,b,x,y);
cout << "x = " << x << "y = " << y << endl;
}
return 0;
}
