Pagini recente » Cod sursa (job #3158910) | Cod sursa (job #2975697)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
long long cmmdc(long long a, long long b) {
long long r;
while (b) {
r = a % b;
a = b;
b = r;
}
return a;
}
pair<long long, long long> euclidExtins(long long a, long long b) {
if (b == 0) {
return make_pair(1, 0);
}
if (b != 0) {
long long r, c;
r = a % b;
c = a / b;
pair <long long, long long> p0 = euclidExtins(b, r);
long long y = p0.first - c * p0.second;
long long x = p0.second;
return make_pair(x, y);
}
}
int main()
{
int T;
long long a, b, c;
fin >> T;
for (int i = 0; i < T; ++i) {
fin >> a >> b >> c;
long long cm = cmmdc(a, b);
if (c % cm != 0) {
fout << "0 0\n";
}
else {
long long x0 = 0, y0 = 0;
pair<long long, long long> p = euclidExtins(a, b);
fout << p.first * (c / cm) << " " << p.second * (c / cm) << "\n";
}
}
return 0;
}