扩展欧几里得算法与丢番图方程

|

扩展欧几里得算法与丢番图方程

作者：老陈

回顾GCD

代码实现

1
2
3
4
5
typedef long long ll;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a%b) : a;
}
1
2
3
4
5
6
7
8
9
ll gcd(ll a, ll b)
{
	while (b)
	{
		a %= b;
		swap(a, b);
	}
	return a;
}

扩展GCD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//此算法即可求出gcd(a,b)，也可求出x和y
//当 gcd(a,b)=d 时，求绝对值和最小的x,y使得xa+yb=d 。
ll ex_gcd(ll a, ll b, ll &x, ll &y)
{
	if (b > a)
		return ex_gcd(b, a, y, x);
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	else
	{
		ll x1, y1;
		ll res = ex_gcd(b, a%b, x1, y1);
		x = y1;
		y = x1 - a / b * y1;
		return res;
	}
}

注意到达结束条件时，有gcd(a,0) = 1*a+0*b,即(x,y)=(1,0)

丢番图方程

定义：含有两个未知量𝑥, 𝑦且形如𝑎𝑥 + 𝑏𝑦 = 𝑐的方程。

我们本次要讨论的问题:

  1. 寻找方程的一个解
  2. 寻找方程的所有解（通解）
  3. 寻找方程的在某区间内的解及解的个数
  4. 寻找方程的解中 x+y 的最小值

我们将忽略𝑎 = 𝑏 = 0的情形，因为这种情况下不是无穷多解就是无解。（取决于𝑐的取值）

丢番图方程——寻找一个解

1
2
3
4
5
6
7
8
9
10
11
bool find_any_solution(ll a, ll b, ll c, ll &x0, ll &y0, ll &g)
{
	g = ex_gcd(abs(a), abs(b), x0, y0);
	if (c % g)
		return false;
	x0 *= c / g;
	y0 *= c / g;
	if (a < 0) x0 = -x0;
	if (b < 0) y0 = -y0;
	return true;
}

丢番图方程——寻找所有解（通解）

丢番图方程——寻找方程的在某区间内的解及解的个数

例题：Romantic（HDU 2669）

题目

解析

很明显，本题需要使用扩展欧几里得算法来解决

有解的条件？

如何获得𝑋 > 0的最小解？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
	int a, b;
	ll x, y;
	while (~scanf("%d %d", &a, &b))
	{
		int d = ex_gcd(a, b, x, y);
		if (d != 1)
		{
			cout << "sorry" << endl;
			continue;
		}
		while (x <= 0)
		{
			x = x + b;
			y = y - a;
		}
		cout << x << ' ' << y << endl;
	}
	return 0;
}

例题2：Get AC in one go（Codechef）

题目

解析

代码中a * b - a - b的证明：

https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
	int t;
	while (~scanf("%d", &t))
	{
		for (int i = 0; i < t; i++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			int g = gcd(a, b);
			if (g == 1)
				printf("%d\n", a * b - a - b);
			else
				printf("-1\n");
		}
	}
	return 0;
}