Даны два числа А и B. Найти их наибольший общий делитель

[_Лето_]

Задача: Даны два числа А и B. Найти их наибольший общий делитель и числа U и V при которых A*U+V*B=НОД(A,B). Не получается решить. Пожалуйста, помогите

#include <iostream>
using namespace std;
/*int main()
{
    setlocale(LC_ALL, "Russian");
    int a,b,c,x,y;
    cout << "Введите a:";
    cin >> a;
    cout << "Введите b:";
    cin >> b;
  while (b!=0)
    {
      c = a % b;
      a = b;
      b = c;

   }
   d = a;
cout << d;
}*/ 
// то, что выше выводит только НОД(A,B) Следующая функция должна находить нужные числа U и V, чего она почему-то не делает

int gcd (int a, int b, int & x, int & y) {
    setlocale(LC_ALL, "Russian");
     cout << "Введите a:";
    cin >> a;
    cout << "Введите b:";
    cin >> b;
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	int x1, y1;
	int d = gcd (b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	cout << x << ", " << y;
	return d;
}