如何理解扩展欧几里得算法？

Question

请问下列代码中d，x和y的公式是如何通过扩展欧几里得算法得到的。

//裴蜀定理：设a，b为正整数，则关于x，y的方程ax+by=c有整数解当且仅当c是gcd(a,b)的倍数
//ax+by=gcd(a,b)的通解：x=x0+k*b/gcd(a,b)，y=y0-k*a/gcd(a,b)，其中x0，y0为扩展欧几里得的解
//洛谷 P1082 同余方程
//扩展欧几里得算法
int exgcd(int a, int b, int& x, int& y)
{
    if (b == 0)
    {
        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;
    exgcd(a, b, x, y);
    cout << x % b << endl;
    return 0;
}