Pagini recente » Cod sursa (job #2876042) | Cod sursa (job #2460313) | Cod sursa (job #3168741) | Cod sursa (job #438307) | Cod sursa (job #3213187)
#include <bits/stdc++.h>
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
const int NMAX = 1e5 + 30;
const int INF = 0x3f3f3f3f;
int t, a, b, c, x, y, d;
void read()
{
in >> t;
}
void euclid(int a, int b, int &d, int &x, int &y)
{
if (b == 0)
{
d = a; // ultimul rest e 0, returnam penultimul rest si a * 1 + 0 * y = a
x = 1, y = 0;
return;
}
int x1, y1;
// a = b * c + r, unde c = a / b, deci r = a - b * c
euclid(b, a % b, d, x1, y1);
x = y1;
y = x1 - a / b * y1;
}
void solve()
{
while (t--)
{
in >> a >> b >> c, euclid(a, b, d, x, y);
if (c % d == 0) // transformam ecuatia a*x+b*y = d in a*u + b*v = c, prin inmultire cu c/d daca se imparte exact
out << x * (c / d) << ' ' << y * (c / d) << '\n';
else
out << 0 << ' ' << 0 << '\n';
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
read();
solve();
return 0;
}