Расширенный алгоритм Евклида - решение

В помощь: Википедия, см. "Расширенный алгоритм Евклида и соотношение Безу".

#include "stdafx.h"

#include <iostream>

using namespace std;

unsigned int NOD_euqlid_ext(unsigned int a, unsigned int b, int& x, int& y)

{

int x2 = 1, x1 = 0;

int y2 = 0, y1 = 1;

unsigned int q, r;

while (b > 0) {

q = a / b;

r = a - b * q;

x = x2 - q * x1;

y = y2 - q * y1;

a = b;

b = r;

x2 = x1;

x1 = x;

y2 = y1;

y1 = y;

}

x = x2;

y = y2;

return a;

}

int _tmain(int argc, _TCHAR* argv[])

{

unsigned int a, b;

cin >> a;

cin >> b;

unsigned int d;

int x, y;

d = NOD_euqlid_ext(a, b, x, y);

cout << d << "\t" << x << "\t" << y << endl;

system("pause");

return 0;

}