#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;

void sito(bool *tab, unsigned int n)
{
	for (int i=2; i*i<=n; i++) //przeszukujemy kolejnych kandydatów na pierwsze
    {							//wystarczy sprawdziæ do pierwiastka z n
    							// i<=sqrt(n) - podnosz¹c do kwadratu mamy
    							// i*i <= n
        if(!tab[i])				//jesli liczba jest pierwsza(ma wartosc 0)
		for (int j = i*i ; j<=n; j+=i) //to wykreslamy jej wielokrotnosci
            tab[j] = 1;			//ustawiaj¹c wartosæ na 1
    }
}
/*
int x, y;
void euklides(int a, int b)
{
	if(b!=0)
	{
		euklides(b, a%b);

		int pom = y;
		y = x  - a/b*y;
		x = pom;
	}
}
*/

/*
int x,y;
int r_count =1;
void euklidesAlgorithm(int a , int b)
{
     int q, r;

     r = a % b;

        if(r!=0 ){
            cout<< "r"<<r_count<<" "<< r <<endl;
            r_count++;

            euklidesAlgorithm(b, r);
            int q = y;
            y = x-a / b*y;
            x = q;

        }*/
        /*
int rCounter = 1;
int euklidesAlgorithm(int a, int b, int& x, int& y, bool start){

    static int staticX[2] = {};
	static int staticY[2] = {};
    int q, r, r2, q2;

    r = a % b ;
    q = (a - r) / b;
    cout<< "r"<<rCounter<<" = "<<a << " - "<< q<< " * "<< b<< " = "<< r<< "\n";
    rCounter++;
    if( r != 0){
        return euklidesAlgorithm(b , r);
    }
    return b;
}*/


int euklidesAlgorithm(int a, int b, int& x, int& y, bool start= true)
{
	static int staticX[2] = {};
	static int staticY[2] = {};

	int r = a % b;
	int q = (a - r) / b;

	std::cout << a << " = " << q << " * " << b << " + " << r << "\n";

	if (r != 0) {
		// Wyczyść wartości x i y, jeśli jest to pierwsze wywołanie funkcji
		if (start) {
			staticX[0] = 0;
			staticX[1] = 1;
			staticY[0] = 1;
			staticY[1] = -q;
		}
		else {
			int tempX = staticX[1];
			staticX[1] = staticX[0] - staticX[1] * q;
			staticX[0] = tempX;

			int tempY = staticY[1];
			staticY[1] = staticY[0] - staticY[1] * q;
			staticY[0] = tempY;
		}

		std::cout << "x = " << staticX[1] << " y = " << staticY[1] << "\n\n";

		return euklidesAlgorithm(b, r, x, y, false);
	}

	x = staticX[1];
	y = staticY[1];

	return b;
}




    /* cout<< a/b<<endl;
     r1 = a%b;
     cout<< " r1  = "<< r1;
     r2 = b%r1;
     cout<< " r2  = "<< r2<<endl;
     r3 = r1%r2;
      cout<< " r3  = "<< r3<<endl;
      q1= (a -r1)/b;
      cout<< " q1: " <<q1<<endl;
      q2 = (b-r2)/r1;
      cout<<"q2 = "<< q2<<endl;
      q3 = (r1- r3) / r2<<endl;
      cout<< "q3 = "<<q3<<endl;


}
*/

int main()

{
    int x, y;
    cout<< " \nWpisz liczbe  a i b"<<endl;
    int a = 1920;
    int b = 162;
    int result  = euklidesAlgorithm(a,b,x,y );

    cout<< "NWD ( "<<a<<", "<<b<< " )"<<" = "<< result;





    /*
    x = 1, y = 0;
	int a, b;

	cout<<"Podaj liczby: ";
	cin>>a>>b;

	euklides(a, b);

	cout<<"nwd("<<a<<", "<<b<<") = "
	<<a<<" * "<<x<<" + "<<b<<" * "<<y<<" = "
	<<a*x+b*y<<endl;
*/


/*
	int n;
	bool *tab;

	cout<<"Podaj zakres górny przedzia³u: ";
	n=2800000;

	tab = new bool [n+1];
	for(int i=2; i<=n; i++) //zerowanie tablicy
		tab[i] = 0;

	sito(tab, n); //przesianie liczb

	cout<<"Kolejne liczby pierwsze z przedzia³u [2.."<<n<<"]: ";
    int primecounter=0;

    cout<< "Wpisz liczbe n: "<<endl;
    int d;
    cin>>d;
    unsigned long long int liczba;
	for(int i=2;i<=n;i++)
		if(!tab[i] && primecounter<d){
		//	cout<<i<<" ";
            liczba=i;
			primecounter++;
		}

    cout<< endl;
    cout<<"N-ta liczba pierwsza:  "<< liczba;

	delete []tab;*/

	cin.get();

	system("pause");
    return 0;
}