Pagini recente » Cod sursa (job #215554) | Cod sursa (job #1654749) | Cod sursa (job #2228836) | Cod sursa (job #2320080) | Cod sursa (job #2437899)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
int sign(int x)
{
return x < 0 ? -1 : 1;
}
int main()
{
int t;
in >> t;
while(t--)
{
int a, b, c;
in >> a >> b >> c;
pair<int,int> ab = {max(abs(a),abs(b)), min(abs(a),abs(b))};
int gcd = __gcd(abs(a),abs(b));
if(c % gcd != 0)
{
out << "0 0" << '\n';
continue;
}
vector<pair<int,int>> V = {
{1,0},
{0,1}
};
if(a == 0)
{
out << 0 << ' ' << c/b << '\n';
continue;
}
if(b == 0)
{
out << c/a << ' ' << 0 << '\n';
continue;
}
int n = 2;
int q1 = ab.first;
int q2 = ab.second;
int r = q1 % q2;
while(r)
{
int q = q1/q2;
r = q1%q2;
q1 = q2*q + r;
q1 = q2;
q2 = r;
int x = V[n-2].first - q*V[n-1].first;
int y = V[n-2].second - q*V[n-1].second;
pair<int,int> p = {x,y};
V.push_back(p); n++;
if(r == gcd) break;
}
int x = V[n-1].first;
int y = V[n-1].second;
int alfa = c/gcd;
if(abs(a) == ab.second) swap(x,y);
x *= alfa; y *= alfa;
x *= sign(a); y *= sign(b);
out << x << ' ' << y << '\n';
}
return 0;
}