#define fisier "ULTRA"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
const int aleatoriu = 0;
void _sol(int a, int b, int c, int& x, int& y)
{
if (!a && !b)
{
x = y = 0;
return;
}
if (!a)
{
if (c % b)
x = y = 0;
else
x = aleatoriu, y = c / b;
return;
}
if (!b)
{
_sol(b, a, c, y, x);
return;
}
_sol(b, a % b, c, y, x);
y -= (a/b)*x;
}
void sol(int a, int b, int c, int& x, int& y)
{
if (a < b)
_sol(b, a, c, y, x);
else
_sol(a, b, c, x, y);
}
int main()
{
int t; in >> t;
while (t--)
{
int a, b, c, x = 0, y = 0;
in >> a >> b >> c;
sol(a, b, c, x, y);
out << x << ' ' << y << '\n';
}
}
/*
24x + 15y = 147
24*6 = 144
15*0 = 0
adaugam un 24 si scadem 15 pana cand avem un numar mai mic decat 15. obtinem un net de +9
24 % 15 = 9
merge de 0 ori
facem ce am facut mai sus si -scadem- numarul mai mic decat 15 (care este 9)
adica din x scadem 1
si la y adaugam 24 / 15 care este 1
daca punem un 15, si scadem un 9 (adica scoatem un 24 si punem un 15). obtinem un net de +6
15 % (24 % 15) = 6
merge de 0 ori
defapt putem face recursia asta pana la infinit pentru ca operandul din dreapta mereu va scadea
ia sa vedem daca facem numai cu 15
15 % (15 % (24 % 15)) = 15 % 6 = 3
15 % (15 % (15 % (24 % 15))) = 15 % 3 = 0
in ritmul asta nu putem ajunge decat pana la net de +3
algoritmul pentru net minim pozitiv obtinut este:
ia un 15, pune un 24 => net de +9
pune un 15, ia un 24, pune un 15 => net de +6
(fa asta de 2 ori: (ia un 15, pune un 24, ia un 15)), pune un 15 => net de +3
ia sa vedem cu 24
24 % (24 % 15) = 6
24 % (24 % (24 % 15)) = 0
tot nu ajungem nicaieri, si totusi solutie exista
solutia este sa punem 33 de 24 si sa luam 43 de 15
33*24 - 43*15 = 147
sa vedem ce se intampla:
se adauga 6 de 24 pentru a ajunge la 144
se adauga odata 24, se ia un 15 si se ajunge la ...
ma ia stai putin ce fac aici
ce ar fi sa fac un algoritm recursiv
sol(a, b, c) = (x, y) pereche de doi intregi solutie
sol(a, b, c) poate sa fie egala cu (c/a, 0) + sol(a, b, c - c/a)
// unde adunarea unei perechi (n, m) + (e, f) inseamna perechea (n+e, m+f)
sau poate sa fie egala cu (0, c/b) + sol(a, b, c - c/b)
sau poate sa fie egala cu {
p = sol(b, a % b, c)
x = p.y
y = p.x - (a/b)*p.y
return (x, y)
}
o sa o scriu intr-un program
*/