基本知识
扩展欧几里德算法即 exgcd，一般用来求形如 \(ax+by=\gcd(a,b)\) 的二元一次不定方程的整数解。以下为了方便将用 \(d\) 代替 \(\gcd(a,b)\)。
考虑 \(\gcd(b,a\bmod b)=\gcd(a,b)\)，，于是递归，边界是 \(b=0\)，此时方程是 \(ax=a\)，显然 \(x=1\)，\(y\) 没有限制。
再考虑 \(bx+(a\bmod b)y=d\) 的解如何转变成 \(ax+by=d\) 的，我们设 \(bx+(a\bmod b)y=d\) 的解 \(x=y_0,y=x_0\)，于是 \((a\bmod b)x_0+by_0=d\)，因此我们可以令 \(ax+by=d\) 的解 \(x=x_0\)，注意到 \(a=b\times\lfloor \frac{a}{b}\rfloor+a\bmod b\)，因此 \(ax+by=d\) 和 \((a\bmod b)x_0+by_0=d\) 两式相减得 \(b\times\lfloor \frac{a}{b}\rfloor x_0+b(y-y_0)=0\)，变一下形得 \(y=y_0-\lfloor \frac{a}{b}\rfloor x_0\)。