Pagini recente » Cod sursa (job #1646109) | Cod sursa (job #690235) | Cod sursa (job #2569033) | Cod sursa (job #533073) | Cod sursa (job #2972131)
#include <cstdio>
#include <memory>
using namespace std;
class Solver{
private:
int N;
public:
Solver() {
freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
}
~Solver() {
fclose(stdin);
fclose(stdout);
}
void readData() {
scanf("%d", &N);
}
void extendedEuclid(long long A, long long &X, long long B, long long &Y, long long &D) {
if (B == 0) {
// GCD(A, 0) = A
// A * 1 + B * 0 = GCD(A,B)
// A * 1 + 0 * 0 = A
D = A;
X = 1;
Y = 0;
return;
}
long long _X, _Y;
extendedEuclid(B, _X, A%B, _Y, D);
// B * _X + (A-[A/B]*B) * _Y = D
// A * X + B * Y = D
X = _Y;
Y = _X -A/B*_Y;
}
void computeAnswers() {
long long A, X, B, Y, D, C;
for (int i = 0; i < N; ++i) {
scanf("%lld%lld%lld", &A, &B, &C);
extendedEuclid(A, X, B, Y, D);
/// A*X + B*Y = D
/// A*X*C + B*Y*C = D*C
/// (A*X*C)/D + (B*Y*C)/D = C
/// A*((X*C)/D) + B*((Y*C)/D) = C
if((X*C) % D == 0 && (Y*C) % D == 0)
printf("%lld %lld\n", X*C/D, Y*C/D);
else
printf("0 0\n");
}
}
};
int main()
{
unique_ptr<Solver> s = make_unique<Solver>();
s->readData();
s->computeAnswers();
return 0;
}