Equacions diofàntiques X52077

Una equació diofàntica de primer ordre, és una equació del tipus:

$$ax + by = c$$

on $a,b,c$ són enters fixats i $x,y$ només poden prendre valors enters. Donats $a,b,c$ troba $x$ i $y$ la solució de l’equació diofàntica amb $x \geq 0$ i $x$ el més petit possible. En cas que l’equació no tingui solució indica-ho.

Entrada

L’entrada consisteix en diversos casos, cada cas consta d’una línia, hi ha com a molt $10^5$ línies. Cada línia conté tres enters $a, b, c$ amb $1 \leq a,b,c \leq 10^8$.

Sortida

Escriviu dos enters per línia: $x$ i $y$, les solucions de l’equació diofàntica amb $x \geq 0$ i $x$ el més petit possible. En cas que l’equació no tingui solució escriviu "Sense solucio".

Pista

Utilitza l’algoristme d’Euclides ampliat.