当前位置：首页 > news >正文

扩展欧几里得算法【Exgcd】的内容与题目应用

news 来源：原创 2025/8/21 16:04:29

1.简介

exgcd的目的是表示出二元一次不定方程的通解。
形式化地，exgcd算法就是输入a，b，c的值，返回一组x，y，满足 $a x + b y = c$ 。

2.1方程无整数解的情况

当 c 不能被 a ，b最小公倍数的整除时候，方程无整数解。反之，有整数解。（此条性质又名裴蜀定理）。

2.2把求解 $a x + b y = c$ 转化为求解 $a x + b y = g c d (a, b)$

$a x + b y = c$ ，则 $2 a x + 2 b y = 2 c ， na x + nb y = n c$ 。
$a x + b y = c$ 对应的解是 $a x + b y = g c d (a, b)$ 的解的整数倍，更具体一些是 $c / g c d (a, b)$ 倍

所以，只需要找到 $a x + b y = g c d (a, b)$ 的解，将其乘以 $c / g c d (a, b)$ ，就找到了

2.3 求解方程 $a x + b y = g c d (a, b)$

先人给出了几个神秘的黑色箱子，丢入a，b，c，就吐出满足 $a x + b y = c$ 的一组x，y。

2.3.1 黑箱a(用lamdba语法)

int x,y;
auto exgcd = [&](auto &&self,int a,int b) -> void
{if(b == 0){x = 1;y = 0;return;}self(self,b,a%b);int t = x;x = y;y = t - a/b*y;
};  
exgcd(exgcd,a,b);//运行完此行，x，y就已经存的是合法值了

2.3.1 黑箱b（没有lambda）

// 不想&x,&y可以开全局变量
int Exgcd(int a, int b, int &x, int &y) {if (!b) {x = 1;y = 0;return a;}int d = Exgcd(b, a % b, x, y);int t = x;x = y;y = t - (a / b) * y;return d;//返回值d是顺带求出的gcd(a,b)
}

写个4~5道就背住了。
有兴趣看看证明
做完题目就会发现，题目不涉及证明，不涉及黑箱种类，但本文中的通过代码只给了黑箱a的

2.4 题目仅需任意一组合法解（特解）

x *= c/__gcd(a,b)，y *= c / __gcd(a,b) //把倍数乘回去，现在就是真·特解了

任意一组，直接输出exgcd算法求出来的这组即可。

2.5题目需要满足 $x > m$ 的最小解（通解）

为了大于x的最小解，我们需要先求出特解，再增大(减小)x，减小(增大)y，使得等式仍然成立，且x恰好大于m。
观察得到如下性质：
记 $x_1,y_1$ 是exgcd算法返回的解

若 $a(x_1+t_x) + b(y_1+t_y) = c$ ，则 $t_xa = -t_yb$

所以，当 $x_2 = x_1 + k\frac{b} {gcd(a,b)} ，y_2 = y_1 - k\frac{a} {gcd(a,b)},$ k为整数，时，仍然有 $a x + b y = c$
可以回带验证。
那么，找出 $x_1$ 加减多少个 $\frac{b} {gcd(a,b)}$ 恰好大于m,也就找到了 $x > m$ 的最小解
其实这个过程是在求通解。

int d = __gcd(a,b),tx = b/d,ty = a/d;
int k;
if(tx > 0) k = ceil((m-x)/tx);
else k = floor((m-x)/tx);
x += tx*k;
y -= ty*k;

3.模板题

题目提交链接

P5656 【模板】二元一次不定方程 (exgcd)

题目描述

给定不定方程

$a x + b y = c$

若该方程无整数解，输出 $- 1$ 。
若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中 $x$ 的最小值，所有正整数解中 $y$ 的最小值，所有正整数解中 $x$ 的最大值，以及所有正整数解中 $y$ 的最大值。
若方程有整数解，但没有正整数解，你需要输出所有整数解中 $x$ 的最小正整数值， $y$ 的最小正整数值。

正整数解即为 $x, y$ 均为正整数的解， $\boldsymbol{0}$ 不是正整数。
整数解即为 $x, y$ 均为整数的解。
$x$ 的最小正整数值即所有 $x$ 为正整数的整数解中 $x$ 的最小值， $y$ 同理。

输入格式

第一行一个正整数 $T$ ，代表数据组数。

接下来 $T$ 行，每行三个由空格隔开的正整数 $a, b, c$ 。

输出格式

$T$ 行。

若该行对应的询问无整数解，一个数字 $- 1$ 。
若该行对应的询问有整数解但无正整数解，包含 $2$ 个由空格隔开的数字，依次代表整数解中， $x$ 的最小正整数值， $y$ 的最小正整数值。
否则包含 $5$ 个由空格隔开的数字，依次代表正整数解的数量，正整数解中， $x$ 的最小值， $y$ 的最小值， $x$ 的最大值， $y$ 的最大值。

输入输出样例 #1

输入 #1

输出 #1

4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56

说明/提示

【数据范围】

对于 $100\%$ 的数据， $\le T \le 2 \times {10}^5$ ， $\le a, b, c \le {10}^9$ 。
【本博客额外提示】

注意爆 int 的问题，使用long long 类型

思路：

正整数解中x的最小值，就是 x > 0 的最小值
x 最大时 y最小，x最小时y最大

通过代码

#include<bits/stdc++.h>
#define int long long
using namespace std;void solve()
{int x,y;int a,b,c;cin >> a >> b >> c;int d = __gcd(a,b);if(c % d != 0){cout << -1 << '\n';return;}auto exgcd = [&](auto &&self,int a,int b){if(b == 0){x = 1;y = 0;return;}self(self,b,a%b);int t = x;x = y;y = t - a/b*y;};exgcd(exgcd,a,b);x = x * c / d,y = y * c / d;int tx = b/d,ty = a/d;int k = ceil((1.0-x)/tx);x += tx*k;y -= ty*k;if(y <= 0){int ymin=y+ty*ceil((1.0-y)/ty);cout << x << ' ' << ymin << '\n';}else{cout << (y-1)/ty + 1 <<' ' << x << ' ' << (y - 1) % ty + 1 << ' ' << x + (y-1)/ty *tx << ' ' << y << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t --) solve();return 0;
}

4.练习

[2022CCPC哈尔滨E]
[2022ICPC杭州A]
[2023湖北I]
[CF927G]
[2023ICPC网络赛(1) K]