Zadanie : euklid-b
Zadanie

Poniższa tabela przedstawia wszystkie wartości obliczone podczas wykonywania rekurencyjnej wersji rozszerzonego algorytmu Euklidesa dla liczb 231 i 30: 

i |  Ri     di    xi    yi
-------------------------------------------------
0 |  231    -     -     -
1 |  30     7     3     -23
2 |  21     1     -2    3
3 |  9      2     1     -2
4 |  3      3     0     1
5 |  0      -     1     0

Poczynając od drugiego wiersza wartości di otrzymujemy z wzoru di=Ri-1 div Ri.
W ostatnim wierszu liczby xi i yi są wpisane na stałe. W każdym z poprzednich wierszy liczby te otrzymujemy z wzorów: 

xi=yi+1
yi=xi+1-di*yi+1

Ze wzorów wynika, iż aby uzyskać dla pary liczb (231,30) rozwiązanie (x1,y1), należy wcześniej uzyskać dla pary (30, 231 mod 30) rozwiązanie (x2,y2), itd. przy czym dla pary (x,0) rozwiązaniem jest para w ostatnim wierszu (1,0).

Napisz program, który korzystając z powyższej rekurencyjnej wersji uogólnionego algorytmu Euklidesa wyznaczy rozwiązanie równania x*a+y*b=NWD(a,b).
W programie zdefiniuj rekurencyjną funkcję o nagłówku: 

void euklides(int a, int b, int &x, int &y);
Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite a i b z zakresu 1..200, przy czym a>=b.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać równanie zgodnie z przykładem. W wierszu drugim należy zapisać sumę wszystkich obliczonych wartości yi występujących w tym algorytmie.

Przykład

Dla danych podanych na wejściu:

39 29

Poprawną odpowiedzią jest wyjście:

3*39-4*29 = 1
-1

Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5

Opcje zadania:

Biblioteki         : iostream iomanip cmath 
Limit czasu        : 0.25 s
Limit pamięci      : 32 MB
Słowa niedozwolone :