扩展欧几里得算法

#include<cmath>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
	if(!b)
	{
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x; 
	return d;
}
int main() {
	int a, b, x, y;
	cin >> a >> b;
	int d = exgcd(a, b, x, y);
	printf("%d * %d + %d * %d = %d",a, x, b, y, d);
}