欧几里得算法

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

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

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

变题

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

数学思维:

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

裴蜀(贝祖)等式

对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程(称为裴蜀(贝祖)等式)
ax+by=m(d) 有整数解时候 当前仅当m是d(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;
    }
}

GtiHub查看代码

乘法逆元

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天。上述全是自己一个字一个字梳理码的。记得这么详细 便于自己复习和有需求的朋友理解。 如有问题 欢迎支教！！

练习题