Pagini recente » Cod sursa (job #580796) | Cod sursa (job #2723623) | Cod sursa (job #288355) | Cod sursa (job #477706) | Cod sursa (job #2437884)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
int main()
{
int t;
in >> t;
while(t--)
{
int a, b, c;
in >> a >> b >> c;
pair<int,int> ab = {max(a,b), min(a,b)};
int gcd = __gcd(a,b);
if(c % gcd != 0)
{
out << "0 0" << '\n';
continue;
}
vector<pair<int,int>> V = {
{1,0},
{0,1}
};
if(a == ab.second) swap(V[0],V[1]);
int n = 2;
int q1 = ab.first;
int q2 = ab.second;
int r = q1 % q2;
while(r > 1)
{
int q = q1/q2;
r = q2%q1;
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++;
}
int x = V[n-1].first;
int y = V[n-1].second;
int alfa = c/gcd;
x *= alfa; y *= alfa;
out << x << ' ' << y << '\n';
}
return 0;
}