Pagini recente » Cod sursa (job #449245) | Cod sursa (job #2675810) | Cod sursa (job #231208) | Cod sursa (job #687166) | Cod sursa (job #2692177)
#include <bits/stdc++.h>
#define int int64_t
#define cin fin
#define cout fout
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int gcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g)
{
g = 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;
}
int32_t main()
{
int t, a, b, c, x, y, d;
cin >> t;
for (int i = 1; i <= t; i++)
{
cin >> a >> b >> c;
int ok = 0;
if (a > b)
swap(a, b), ok = 1;
if (a == 0 && b == 0)
{
cout << "0 0\n";
}
else if (a==0)
{
int x=0,y=0;
if (c%b==0) y=c/b;
if (ok) swap(x,y);
cout<<x<<" "<<y<<'\n';
}
else if (b==0)
{
int x=0,y=0;
if (c%a==0) y=c/a;
if (ok) swap(x,y);
cout<<x<<" "<<y<<'\n';
}
else if (find_any_solution(a, b, c, x, y, d))
{
int bd = b / d;
int ad = a / d;
int aux = y / ad;
y = y - aux * ad;
x = x + aux * bd;
if (ok)
swap(x, y);
cout << x << " " << y << '\n';
}
else
{
cout << "0 0\n";
}
}
return 0;
}