【普及】扩展欧几里得算法
题目描述
给定不定方程
若该方程无整数解，输出 0 0
若该方程有整数解，请输出 任意一组解
- 虽然原理讲了很多，但代码写起来很简单！！
（点击展开）大家可以参考下面的扩展欧几里得算法
#include <bits/stdc++.h>
using namespace std;
/*--------------------------------- 扩展欧几里得 begin ---------------------------------------------*/
template<typename T>
T extgcd(T a, T b, T &x, T &y) {
if (!b) {
x = 1, y = 0;
return a;
}
T x0, y0;
T g = extgcd(b, a % b, x0, y0);
x = y0, y = x0 - (a / b) * y0;
return g;
}
/*--------------------------------- 扩展欧几里得 end -----------------------------------------------*/
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
i64 T, a, b, c, x, y;
cin >> T;
while (T--) {
cin >> a >> b >> c;
i64 d = extgcd(a, b, x, y);
if (c % d) cout << "0 0" << '\n';
else cout << x * c / d << ' ' << y * c / d << '\n';
}
return 0;
}
输入格式
第一行一个正整数 ，代表数据组数。
接下来 行，每行三个由空格隔开的正整数 。
输出格式
行。
若该行对应的询问无整数解，输出 0 0
若该方程有整数解，请输出 和 代表 任意一组解
7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432
6 8
2 0
0 0
1 30399
34 -8
0 0
12 56
提示
【样例 #1 解释】
- 方程无解
- 方程无解
- 其中有的方程不止一个解，输出任意一个解就好