Pagini recente » Cod sursa (job #1868617) | Monitorul de evaluare | Cod sursa (job #489148) | Cod sursa (job #2709830) | Cod sursa (job #2904898)
#include <fstream>
#include <iostream>
#define LL int
using namespace std;
pair<LL,LL> bezout(LL a, LL b){
pair<LL,LL> ans;
int swapped = 0, minusa = 1, minusb = 1;
LL q, r;
if(a < 0){
a = -a;
minusa = -1;
}
if(b < 0){
b = -b;
minusb = -1;
}
if(a < b){
swap(a, b);
swapped = 1;
}
if(b == 0){
ans = {1, 0};
}
else{
q = a / b;
r = a % b;
pair<LL,LL> MN = bezout(b, r);
ans = {minusa * MN.second, minusb * (MN.first - q * MN.second)};
}
if(swapped)
swap(ans.first, ans.second);
return ans;
}
int main(){
ifstream fin;
ofstream fout;
fin.open("euclid3.in");
fout.open("euclid3.out");
LL a, b, c, n, d, x, y;
pair<LL,LL> bez;
fin >> n;
for(int i = 1; i <= n; ++i){
fin >> a >> b >> c;
bez = bezout(a, b);
x = bez.first, y = bez.second;
d = a*x + b*y;
if(c % d)
fout << "0 0\n";
else
fout << x*(c / d) << " " << y*(c / d) << "\n";
}
}