Pagini recente » Cod sursa (job #2983297) | Cod sursa (job #642542) | Cod sursa (job #826115) | Cod sursa (job #2293086) | Cod sursa (job #1220894)
#include <iostream>
#include <cstdio>
#include <utility>
using namespace std;
int euclid(int a, int b){
if(b == 0) return a;
int c;
while(b){
c = a;
a = b;
b = c % b;
}
return a;
}
// d = gcd(a, b) = a * x + b * y = d' = gcd(b, a % b) = b * x' + (a % b) * y'
// d = a * x + b * y = b * x' + (a - [a/b] * b) * y'
// d = a * x + b * y = a * y' + (x' - [a/b]*y') * b
// (d, x, y) = (d', y', x' - [a/b]*y')
pair<int, int> euclid_ext(int a, int b){
if(b == 0) return make_pair(1,0);
pair<int, int> p;
p = euclid_ext(b, a % b);
return make_pair(p.second, p.first - a/b * p.second);
}
int main(){
//freopen("euclid3.in", "r", stdin);
//freopen("euclid3.out", "w", stdout);
int t, c, a, b, d;
cin >> t;
for(int i = 0; i < t; i++){
cin >> a >> b >> c;
if(c % (d = euclid(a,b)) == 0){
pair<int, int> r = euclid_ext(a, b);
cout << r.first * (c/d) << " " << r.second * (c/d) << "\n";
}else{
cout << "0 0\n";
}
}
return 0;
}