b站事故中的辗转相除法
0 / 0 / 创建于 2年前 /
我们只希望世界和平 的个人博客
前几天看到到挺多关于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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号