Sweet Snippet 系列之扩展欧几里得算法

╰+哭是因爲堅強的太久メ 2021-12-14 07:09 182阅读 0赞

> 扩展欧几里得算法的简单实现

扩展欧几里得算法是欧几里得算法(辗转相除法)的扩展,欧几里得算法可以用于求解两个自然数(记为  a a a 和  b b b)的最大公约数,而扩展欧几里得算法不仅可以求出  a a a 和  b b b 的最大公约数,还能同时计算出两个整数  x x x 和  y y y, 使它们满足等式(等式中的  g c d ( a , b ) gcd(a, b) gcd(a,b) 即表示  a a a 和  b b b 的最大公约数):

a x + b y = g c d ( a , b ) ax + by = gcd(a, b) ax\+by=gcd(a,b)

说到算法步骤的话,扩展欧几里得算法其实是逆向运用了欧几里得算法(辗转相除法)的中间结果,有兴趣的朋友可以看看 [wiki][] 上的计算案例,在此我们简单推导一下用于计算  x x x 和  y y y 的递推公式,以方便我们编写代码:

首先是基础条件( b = 0 b = 0 b=0 的情况)

g c d ( a , 0 ) = a a ∗ 1 + 0 ∗ a n y = g c d ( a , 0 ) = a = > \{ x = 1 y = 0 \\begin\{aligned\} & gcd(a, 0) = a \\\\ & a \* 1 + 0 \* any = gcd(a, 0) = a => \\\\ \\end\{aligned\} \\\\ \\left\\\{ \\begin\{aligned\} & x = 1 \\\\ & y = 0 \\end\{aligned\} \\right. gcd(a,0)=aa∗1\+0∗any=gcd(a,0)=a=>\{ x=1y=0

当  b = 0 b = 0 b=0 的情况下,我们取  g c d ( a , 0 ) = a gcd(a, 0) = a gcd(a,0)=a, 此时  x = 1 x = 1 x=1,  y y y 为任意值 都可满足之前的等式,简单起见,我们取  x = 1 , y = 0 x = 1, y = 0 x=1,y=0.

现在我们知道基础条件下  x x x 和  y y y 的取值了,我们看看如何递推求解下一步的  x x x 和  y y y:

a x + b y = g c d ( a , b ) b x ′ + ( a % b ) y ′ = g c d ( b , a % b ) ∵ g c d ( a , b ) = g c d ( b , a % b ) ∴ a x + b y = b x ′ + ( a % b ) y ′ = b x ′ + ( a − ⌊ a / b ⌋ b ) y ′ = a y ′ + b ( x ′ − ⌊ a / b ⌋ y ′ ) = > \{ x = y ′ y = x ′ − ⌊ a / b ⌋ y ′ \\begin\{aligned\} & ax + by = gcd(a, b) \\\\ & bx&\#x27; + (a \\% b)y&\#x27; = gcd(b, a \\% b) \\\\ & \\because gcd(a, b) = gcd(b, a \\% b) \\\\ & \\therefore ax + by = bx&\#x27; + (a \\% b)y&\#x27; = \\\\ & bx&\#x27; + (a - \\lfloor a / b \\rfloor b)y&\#x27; = ay&\#x27; + b(x&\#x27; - \\lfloor a / b \\rfloor y&\#x27;) => \\end\{aligned\} \\\\ \\left\\\{ \\begin\{aligned\} & x = y&\#x27; \\\\ & y = x&\#x27; - \\lfloor a / b \\rfloor y&\#x27; \\end\{aligned\} \\right. ax\+by=gcd(a,b)bx′\+(a%b)y′=gcd(b,a%b)∵gcd(a,b)=gcd(b,a%b)∴ax\+by=bx′\+(a%b)y′=bx′\+(a−⌊a/b⌋b)y′=ay′\+b(x′−⌊a/b⌋y′)=>\{ x=y′y=x′−⌊a/b⌋y′

以上便是  x x x 和  y y y 的递推公式了,有了递推公式,代码就一目了然了(Lua):

-- return { r, x, y }
    function gcd_ex(a, b)
        if b == 0 then
            -- base condition
            return { r = a, x = 1, y = 0 }
         else
             -- recursion operation
             local ret = gcd_ex(b, a % b)
             local t = ret.x
             ret.x = ret.y
             ret.y = t - a // b * ret.y
             return ret
         end
    end

借助[之前][Link 1]的辅助代码,我们就可以简单做测试了:

-- SimplePrintToString is from the previous post
    function dump(tbl, depth)
        return SimplePrintToString(tbl, depth)
    end
    
    print(dump(gcd_ex(47, 30)))

#### 参考资料 ####

*  [wiki][]
 *  [Sweet Snippet系列之 Print Lua Table][Link 1]

[wiki]: https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
[Link 1]: https://blog.csdn.net/tkokof1/article/details/75040943