b站事故中的辗转相除法

前几天看到到挺多关于b站的事故降级。其中弹幕中提到的求最大公约数我觉得还是很好奇的。baidu一下后查到了还是熟悉的名字，辗转相除法。

我当时看到这个函数的反应是，这个函数是咋准确求出最大公约数的🤔️。这个算法如果学校有开设密码学的话或许有人接触过。（完全不记得了）

func _gcd(a, b int64) int64 {
    if b == 0 {
        return a
    }
    return _gcd(b, a%b)
}

这个式子最重要的一点是 gcd(a,b)=gcd(b,a%b)。
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r

a = kb + r

设 d 为 a,b 的最大公约数

a/d = kb/d + r/d

r/d = a/d - kb/d

a/d-kb/d 是整数

所以 可以得到 d 也是 gcd(b,a%b) 最大公约数。

本作品采用《CC 协议》，转载必须注明作者和本文链接