Pagini recente » Cod sursa (job #165788) | Cod sursa (job #2910189) | Cod sursa (job #2433058) | Cod sursa (job #3285852) | Cod sursa (job #1744529)
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <ctime>
using namespace std;
#ifdef INFOARENA
#define TEST 0
#else
#define TEST 1
#endif
struct Input {
long long a, b, c;
};
class ExtendedEuclid {
public:
void Solve(long long a, long long b, long long &d,
long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
d = a;
return;
} else {
long long x0, y0;
Solve(b, a%b, d, x0, y0);
x = y0;
y = x0 - (a/b) * y0;
}
}
};
int main() {
vector<Input> input;
if (TEST) {
input.push_back({24,15,147});
input.push_back({24,16,104});
input.push_back({2,4,5});
} else {
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
int num_tests;
scanf("%d", &num_tests);
for (int i = 0; i < num_tests; ++i) {
long long a,b,c;
scanf("%lld %lld %lld", &a, &b, &c);
input.push_back({a,b,c});
}
}
ExtendedEuclid *instance = new ExtendedEuclid();
for (const Input& in : input) {
long long x, y, d;
instance->Solve(in.a, in.b, d, x, y);
if (in.c % d == 0) {
printf("%lld %lld\n", (in.c / d) * x, (in.c / d) * y);
} else {
printf("0 0\n");
}
}
return 0;
}