寒光博客

欧几里得算法 及其扩展--裴蜀(贝祖)等式解线性方程
欧几里得算法 欧几里得算法,既辗转相除法 求出最大公约数(公因子) public static int g...
扫描右侧二维码阅读全文
24
2019/07

欧几里得算法 及其扩展--裴蜀(贝祖)等式解线性方程

欧几里得算法

欧几里得算法,既辗转相除法
求出最大公约数(公因子)

    public static int gcd(int m,int n){
        return n==0?m:gcd(n,m%n);
    }

复杂度 粗略计算 在O(log max(a,b))以内

变题

挑战程序设计P113 线段上的格点数

数学思维:

垂直距离与横向距离的最大公约数-1。其gcd就是可以划分的段数。


裴蜀(贝祖)等式

对任何整数ab和它们的最大公约数d,关于未知数x和y的线性丢番图方程(称为裴蜀(贝祖)等式)
ax+by=m(d)整数解时候 当前仅当md(ab的最大公约数)的倍数
即gcd(a,c)=d ; ax+by=d
裴蜀(贝祖)等式 有解意味着必然有无穷多个整数解,每组解x,y都被称作裴蜀(贝祖)数
可用扩展欧几里得算法(Extended Euclidean algorithm)求得 x,y。

例如

12x+42y=6 有解
因为12 42 是6的倍数 且6是其最大公约数
(4,-1),(11,-3).. 解都符合 >> 差值 △x=7 △y=2
而化简原式子 => 2x+7y=1 类似于跷跷板关系(一降一升)
所以a的增量(4->11)是7=(b/d) b的增量是2=(a/d)
增量: a=b/gcd b=a/gcd;
特别的,方程 ax+by=1 有整数解当且仅当整数a和b互素.(2,1)(2,3)有解;(2,4)无解

总结就是 只要求出贝祖等式的一个解就等得到无数个解

扩展欧几里得算法

gcd(a,b)
    return b==0?a

观察:

欧几里德算法停止的状态是: a'= gcd , b' = 0 ,(a',b'是递归最后一层时参数的值)
那么,这是否能给我们求解 x y 提供一种思路呢?
a'x + b'y = gcd 此时x=1,y为任意数【此时的a,b不是原来的ab】
因为,这时候,只要 a = gcd 的系数是 1 ,那么只要 b 的系数是 0 或者其他值
(无所谓是多少,反正任何数乘以 0 都等于 0 但是a 的系数一定要是 1),
这时,我们就会有: a'1 + b'0 = gcd

反推

当然这是最终状态,但是我们是否可以从最终状态反推到最初的状态呢?
假设当前我们要处理的是求出 a 和 b的最大公约数,并求出 x 和 y 使得
ax + by= gcd (1),--->要求的
而我们已经求出了下一个状态:b 和 a%b 的最大公约数,并且求出了一组x1 和y1 使得:
bx1 + (a%b)y1 = gcd (2) ,-->下一个状态

先后关系

那么这两个相邻的状态之间是否存在一种关系呢?
求余原理:a%b = k ==> a = b(a/b) +k "/"舍掉余数的除法【int计算机除法】 ==> k=a-(a/b)b
我们知道: a%b = a - (a/b)*b(这里的 “/” 指的是整除,例如 5/2=2 , 1/3=0),
那么,我们可以进一步得到:

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

        = b*x1 + a*y1 – (a/b)*b*y1

        = a*y1 + b*(x1 – a/b*y1)        `……(3)`

对比之前我们的状态,式(3)和式(1):求一组 x 和 y 使得:ax + by = gcd ,是否发现了什么?

这里:

    x = y1

    y = x1 – a/b*y1
 现态是x,y 次态是x1,y1 而次态是已知的
这就是`递推式`,注意x,y是递归过程中的`上一层`,x1,y1是`下一层`(下一个状态)得到的值

递推过程
从最下一层往开始回推 bx1 + (a%b)y1 = gcd (因为找到了gcd)回到观察
而这样反推回去的是 ax+by=d 的解
而我们要的是 =m的解法 又 因为 m是d(a,b的gcd)的倍数
所以 x*(m/gcd) 乘他们差的倍数

通解

    那么通解(t任意是倍数,x加那么y减):
    x=x0`+`(b/gcd)*t 所有的x对b同模
    y=x0`-`(b/gcd)*t 所有的y对a同模

完整代码及测试

package BlueCup.Six_MathQuestion;

public class 欧几里得算法 {
    //中国的辗转相除法 求最大公约自公因子
    //4 是 4 8 的 最大公约数

    static long x, y;//全局变量存储 xy的推算

    public static void main(String[] args) throws Exception {
        //ax+by=ans
        long ans;
        try {
            ans = LinearEquation(2, 3, 1);
            System.out.println(x + "+" + y + "=" + ans);//2x+3y=1 >x=-1 y=1
            ans = LinearEquation(2, 7, 1);
            System.out.println(x + "+" + y + "=" + ans);//2x+7y=1 >x=-3 y=1
            ans = LinearEquation(12, 42, 6);
            System.out.println(x + "+" + y + "=" + ans);//12x+42y=6 >x=-3 y=1
            ans = LinearEquation(12, 42, 5);
            System.out.println(x + "+" + y + "=" + ans);//无解
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }

    /**
     * 欧几里得算法,既辗转相除法
     * 求出最大公约数(公因子)
     */
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    /**
     * 最小公倍数 lowest common multiple*/
    public static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    /**
     * 扩展欧几里得算法
     * 调用完成后的 xy是ax+by=gcd(a,b)的解*/
    public static long ext_gcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long res = ext_gcd(b, a % b);
        //到最后一层开始递推x,y
        //已经最下一次更新了 x0 y0 在b==0时候就初始化了
        long x1 = x;//备份
        x = y;//更新x
        y = x1 - a / b * y;//更新y
//        System.out.println(x + " " + y);测试变化
        return res;
    }

    /**
     * 线性方程
     * ax+by=m 当m是gcd(a,b)的倍数时有解
     * 等价于 ax = m mod b*/
    public static long LinearEquation(long a, long b, long m) throws Exception {
        long d = ext_gcd(a, b);
        if (m % d != 0) throw new Exception("无解");//m不是d的倍数无解
        long t = m / d;//倍数 m是d的几倍
        x *= t;
        y *= t;
        return d;
    }
}

乘法逆元

1.乘法逆元(在维基百科中也叫倒数,当然是 mod p后的,其实就是倒数不是吗?):

如果ax≡1 (mod p),且gcd(a,p)=1(a与p互质),则称a关于模p的乘法逆元为x。

为什么可以用扩展欧几里得求得逆元?

我们都知道模就是余数,比如12%5=12-52=2,18%4=18-44=2。(/是程序运算中的除)

那么ax≡1 (mod p)即ax-yp=1.把y写成+的形式就是ax+py=1,为方便理解下面我们把p写成b就是ax+by=1。
就表示x是a的模b乘法逆元,y是b的模a乘法逆元。然后就可以用扩展欧几里得求了。

知道逆元怎么算之后,那么乘法逆元有什么用呢?

做题时如果结果过大一般都会让你模一个数,确保结果不是很大,而这个数一般是1e9+7,而且这个数又是个素数,
加减乘与模运算的顺序交换不会影响结果,但是除法不行。有的题目要求结果mod一个大质数,如果原本的结果中有除法,比如除以a,那就可以乘以a的逆元替代。
(除一个数等于乘它的倒数,虽然这里的逆元不完全是倒数,但可以这么理解,毕竟乘法逆元就是倒数的扩展)。

结束语

呃,,这个问题我细啃了两天,遇到难题就像放弃, 不过还是咬牙坚持了一下,果然挺过去就是豁然开朗 问题突然变的很简单
一个字 妙啊~!!
还是要相信自己——————想成为大佬的第8天。上述全是自己一个字一个字梳理码的。记得这么详细 便于自己复习和有需求的朋友理解。 如有问题 欢迎支教!!

想成为dalao的第二天

练习题


参考文献
[01]互质 https://baike.baidu.com/item/%E4%BA%92%E8%B4%A8/577412
[02]算法很美 6.5 6.6
本文作者:Author:     文章标题:欧几里得算法 及其扩展--裴蜀(贝祖)等式解线性方程
本文地址:https://dxoca.cn/Algorithm/183.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 13th, 2019 at 01:13 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment