Pagini recente » Cod sursa (job #3232512) | Cod sursa (job #2272763) | Cod sursa (job #2793292) | Cod sursa (job #3234830) | Cod sursa (job #1235615)
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <stack>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
using namespace std;
int main() {
ifstream cin("euclid3.in");
ofstream cout("euclid3.out");
int T; cin >> T;
while(T--) {
int A, B, C;
cin >> A >> B >> C;
if (C % __gcd(A, B)) {
cout << "0 0\n";
} else if(A == 0 && B == 0) {
cout << "0 0\n";
}else {
//a * new_s + b * new_t = gcd(a, b)
//s[i + 1] = s[i - 1] - s[i] * q[i]
//t[i + 1] = t[i - 1] - t[i] * q[i]
int old_s = 1, new_s = 0;
int old_t = 0, new_t = 1;
int a = A, b = B;
while(b != 0) {
int save;
int r = a % b, q = a / b;
save = new_s;
new_s = old_s - new_s * q;
old_s = save;
save = new_t;
new_t = old_t - new_t * q;
old_t = save;
a = b; b = r;
}
cout << old_s * (C / a) << " " << old_t * (C/a) << "\n";
}
}
return 0;
}