Pagini recente » Cod sursa (job #709495) | Cod sursa (job #2230677) | Cod sursa (job #2105670) | Cod sursa (job #2977376) | Cod sursa (job #2565753)
#include <bits/stdc++.h>
#define MAXN 1030
#define FILENAME std::string("euclid3")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");
// A*X + B*Y == 1
int gcd(int A, int B, int &X, int &Y) {
if (B == 0) {
X = 1;
Y = 0;
return A;
} int ans = gcd(B, A%B, X, Y);
int aux = Y;
Y = X - (A/B)*Y;
X = aux;
return ans;
}
// A*X + B*Y == c
// B*p + (A%B)*q == c
// A*X + B*p == c <=> A*X + c - (A%B)*q == c <=> A*X == (A%B)*q
// A*q + B*Y == c <=> (A%B)*q + (A/B)*B*q + B*Y == c <=> c - B*p + B*Y + (A/B)*B*q == c
// Y == p - (A/B)*q
int main()
{
int T; input >> T;
while (T--) {
int a, b, c; input >> a >> b >> c;
int x, y; int v = gcd(a, b, x, y);
if (c%v == 0) output << x*(c/v) << ' ' << y*(c/v) << '\n';
else output << 0 << ' ' << 0 << '\n';
}
return 0;
}