Pagini recente » Cod sursa (job #2581445) | Cod sursa (job #2326973) | Cod sursa (job #2338346) | Cod sursa (job #2903689) | Cod sursa (job #3185807)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a % b);
}
}
void euclid(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
}
else
{
int x0, y0;
euclid(b, a % b, x0, y0);
x = y0;
y = x0 - a / b * y0;
}
}
signed main()
{
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int t;
fin >> t;
while (t--)
{
int a, b, c;
fin >> a >> b >> c;
/// a * z + b * t = c
/// fie d = cmmdc(a, b)
int d = gcd(a, b);
/// daca c % d != 0 nu avem solutii
if (c % d)
{
fout << "0 0\n";
return 0;
}
/// inmultim relatia cu c / d
/// z = c / d * x
/// t = c / d * y
/// a * x + b * y = d
/// fie x0 si y0 a.i.
/// b * x0 + (a % b) * y0 = d
/// a * x + b * y = d
/// daca b = 0 atunci d = a, x = 1, y = 0
/// b * x0 + (a % b) * y0 = a * x + b * y
/// (a % b) * y0 = a * x + b * (y - x0)
/// fie c = a / b
/// (a - b * c) * y0 = a * x + b * (y - x0)
/// a * y0 - b * c * y0 = a * x + b * (y - x0)
/// a * (y0 - x) = b * (c * y0 + y - x0)
/// y0 - x = 0 --> x = y0
/// c * y0 + y - x0 = 0
/// y = x0 - c * y0
int x, y;
euclid(a, b, x, y);
x *= c / d;
y *= c / d;
fout << x << ' ' << y << '\n';
}
return 0;
}