扩展欧几里得算法的一种自顶向下实现

上一次发博客已然是将近四年前，疫情还没开始的时候。
在这段时间里我暂别了OI，但是兜兜转转还是回到了计算机这一我一直向往的领域。
去年这个时候也动笔尝试写过一篇博客，但是工程量似乎比我想象中的要大些，自然烂尾了。
但今天登录的时候意外发现这几年里我的文章零零星星地有人点赞收藏，甚至有人关注我，实在不胜感激。

请注意，这篇博客里的代码实现有些问题，请不要参考代码

言归正传，扩展欧几里得算法是在广义欧几里得除法，也就是辗转相除法的过程中得出裴祖定理$s\cdot a+t\cdot b=(a,b)$中$s$与$t$的方法。
文中我会使用%表示求余

为什么辗转相除法可以得到s和t？

辗转相除法就是反复利用$$a=qb+c,q\in \mathbb{Z}$$时，$$\gcd (a,b)=\gcd (b,c)$$这一定理计算$\gcd (a,b)$的过程。在实际应用中表现为$$a=qb+r$$其中$$q=\lfloor \frac{a}{b}\rfloor ,r=a\%b$$再令$b,r$代替$a,b$进行运算，即$$r_i=q_i\cdot r_{i+1}+r_{i+2}$$
我们发现$r_{i+2}=r_i-q_{i+2}\cdot r_{i+1}$，经过多次代换，我们可以将最终的$r_n$用$q_i$与$a,b$的线性组合表示

如何得到s和t

我们探究这个过程的第一步$a=q_{1}b+a\%b$
$$a\%b=a-q_{1}b$$
在$s_{1}a+t_{1}b=a\%b$中$$s_1=1,t_1=-q_1$$
第二步则是
$$(b\%(a\%b))=b-q_2(a\%b)$$
代换得
$$s_2=-q_2{s}_1,t_2=-q_2{t}_1+1$$
所以我们得到了递推公式：
$$s_1=1,t_1=-q_1$$
$$s_i=-q_i{s}_{i-1},t_i=-q_i{t}_{i-1}+1$$

简略地编写程序如下：

#include
struct tri{
	int g, s, t;
};
tri gcd(int a, int b, int s, int t) {
	if(a % b == 0) return (tri){b, s, t};
	return gcd(b, a % b, -(a / b) * s, -(a / b) * t + 1);
}
int main() {
	int a, b; scanf("%d%d", &a, &b);
	if(a < b) b ^=a, a ^= b, b ^= a;//swap a, b
	tri ans = gcd(b, a % b, 1, -(a / b));
	printf("gcd of %d and %d is %d, while %d * %d + %d * %d = %d\n",
		a, b, ans.g,
		ans.s, a, ans.t, b, ans.s * a + ans.t * b
	);
	main();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这个程序的主体部分在$a<b$时会造成错误的结果，推测可能与我$a,b,s,t$分别对应$b,a\%b,s,t$的偷懒传参方式有关。
这个方法中$s,t$的计算是与$a,b$的变化同向的，故而适合笔算。