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

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

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

ax by=gcd(a,b) ax by = gcd(a, b) ax by=gcd(a,b)

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

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

gcd(a,0)=aa∗1 0∗any=gcd(a,0)=a=>{x=1y=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=0b = 0b=0 的情况下,我们取 gcd(a,0)=agcd(a, 0) = agcd(a,0)=a, 此时 x=1x = 1x=1, yyy 为任意值 都可满足之前的等式,简单起见,我们取 x=1,y=0x = 1, y = 0x=1,y=0.

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

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′ begin{aligned} & ax by = gcd(a, b) & bx' (a % b)y' = gcd(b, a % b) & because gcd(a, b) = gcd(b, a % b) & therefore ax by = bx' (a % b)y' = & bx' (a - lfloor a / b rfloor b)y' = ay' b(x' - lfloor a / b rfloor y') => end{aligned} left{ begin{aligned} & x = y' & y = x' - lfloor a / b rfloor y' 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′​

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

代码语言：javascript复制

-- 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

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

代码语言：javascript复制

-- 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

海外加速 编程算法

0 人点赞