#include <iostream>
int extendedGCD(int a, int b, int &x, int &y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
int x1, y1;
int gcd = extendedGCD(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return gcd;
}
int main() {
int a, b, x, y;
std::cout << "Enter two numbers (space-separated): ";
std::cin >> a >> b;
int gcd = extendedGCD(a, b, x, y);
std::cout << "Extended GCD of " << a << " and " << b << " is: " << gcd << std::endl;
std::cout << "Coefficients (x, y) are: (" << x << ", " << y << ")" << std::endl;
return 0;
}