b站事故中的辗转相除法

Go
前几天看到到挺多关于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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!