欧几里得算法及其扩展算法

欧几里得算法又称辗转相除法,目的就是求两个正整数的最大公约数。

代码模板:

//求最大公约数
public static long gcd(long a,long b){
    return b == 0 ? a : gcd(b,a%b);
}

利用到的原理,(a,b)与(b,a%b)的最大公约相同

扩展欧几里得

扩展欧几里得的一个最重要的作用就是解不定方程。AX+BY = K(得到的x和y只是其中一个解)这个式子有无数个解。

比如2x+7y=1;

我们可以看这个式子,1是2和7的最大公约数,我们利用一种思想,当a = gcd(2,7)时,b = 0,那么这时候的x’ = 1;y’ = 0。然后我们利用上图左下边的两个公式进行反向回求,最终能推出来x和y的值。

公式来源:这也是利用了欧几里得的思想,(a,b)与(b,a%b)的最大公约相同

原公式是ax+by = gcd

a%b = k ==> a = b(a/b)+k “/“舍掉余数的除法, == > k = a - (a/b)b

注意这块b 代表的是之前 a ; (a%b) 代表的是之前的 b

这样我们就可以解释中间那个式子的意思了。

gcd = bx1 + (a - (a/b)b)*y1

​ = ay1 + b(x1 - (a/b)*y1)

我们对比ax + by = gcd

x = y1

y = (x1-(a/b)*y1)

最后一步,我们利用这个公式进行反推,比如最右边的那个式子,是从下到上进行反推的结果。

实现代码:

//    扩展欧几里得求线性方程
//    调用完之后xy是ax+by = gcd(a,b)的解
//    本质上就是一个递归函数
    static long x;
    static long y;
    public static long ext_gcd(long a,long b){
//递归头
        if (b == 0){
            x = 1;
            y = 0;
            return a;
        }
        long res = ext_gcd(a,a%b);
        long x1 = x;    //备份x
//        这里的xy已经被下一层递归更新了利用公式 x = x1,y = x1 - a/b*y
        x = y;
        y = x1 - a /b * y; //更新y
        return res;
    }


算法      算法

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!