Pagini recente » Cod sursa (job #450925) | Cod sursa (job #571099) | Cod sursa (job #1424826) | Cod sursa (job #754901) | Cod sursa (job #3208065)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifndef LOCAL
ifstream in("euclid3.in");
ofstream out("euclid3.out");
#define cin in
#define cout out
#endif
pair<int, int> euclid3(int a, int b) {
// ax + by = g
if(a < 0) {
pair<int, int> xy = euclid3(-a, b); // (-a)x + by = g
int x = xy.first, y = xy.second;
// a (-x) + by = g
return {-x, y};
}
if(b < 0) {
pair<int, int> xy = euclid3(a, -b); // ax + (-b)y = g
int x = xy.first, y = xy.second;
// ax + (-y)b = g
return {x, -y};
}
if(b == 0) return {1, 0};
if(a == 0) return {0, 1};
if(a > b) {
pair<int, int> yx = euclid3(b, a);
int y = yx.first, x = yx.second;
return {x, y};
}
// Cazul mai greu
int k = b / a;
pair<int, int> xpyp = euclid3(a, b - k * a);
int xp = xpyp.first;
int yp = xpyp.second;
int y = yp;
int x = xp - k * yp;
return {x, y};
}
void solve() {
int a, b, c; cin >> a >> b >> c;
int g = __gcd(a, b);
if(c % g != 0) {
cout << "0 0" << '\n';
return;
}
int d = c / g;
pair<int, int> xy = euclid3(a, b);
int x = xy.first, y = xy.second;
x *= d; y *= d;
if(a*x + b*y == -c) {
x = -x; y = -y;
}
const int limita = 2e9;
if(x > limita) {
// trebuie sa gasesc k a.i. x - k * b < limita
// x < k * b + limita
// k > (x - limita) / b
int k = (x - limita) / b + 1;
x -= k * b;
y += k * a;
}
if(y > limita) {
int k = (y - limita) / a + 1;
y -= k * a;
x += k * b;
}
if(x < -limita) {
int k = (-x - limita) / b + 1;
x += k * b;
y -= k * a;
}
if(y < -limita) {
int k = (-y - limita) / a + 1;
y += k * a;
x -= k * b;
}
cout << x << ' ' << y << '\n';
}
int32_t main() {
int t; cin >> t;
while(t--) solve();
}