- 【模板】二元一次不定方程 (exgcd)
题目代码
- @ 2026-8-5 9:53:59
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll xx, yy;
ll g = exgcd(b, a % b, xx, yy);
x = yy, y = xx - a / b * yy;
return g;
}
void solve(){
ll a, b, c;
cin >> a >> b >> c;
ll x, y;
ll g = exgcd(a, b, x, y);
if (c % g != 0) {
cout << "-1\n";
return;
}
x *= c / g, y *= c / g;
a /= g, b /= g, c /= g;
ll x0 = (x % b + b) % b; if (x0 == 0) x0 += b;
ll y0 = (y % a + a) % a; if (y0 == 0) y0 += a;
if (a * x0 >= c) {
cout << x0 << ' ' << y0 << '\n';
return;
}
ll y1 = (c - x0 * a) / b;
ll x1 = (c - b * y0) / a;
ll cnt = (x1 - x0) / b + 1;
cout << cnt << ' ' << x0 << ' ' << y0 << ' ' << x1 << ' ' << y1 << '\n';
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/*
g++ -std=c++17 1.cpp -o 1 && 1 < in.txt > out.txt
g++ -std=c++17 1.cpp -o 1 && ./1 < in.txt > out.txt
*/
0 条评论
目前还没有评论...
信息
- ID
- 556
- 时间
- ms
- 内存
- MiB
- 难度
- 6
- 标签
- 递交数
- 29
- 已通过
- 11
- 上传者