欧几里得算法求最大公约数与贝祖等式(Java)

欧几里得算法，即辗转相除法求最大公约数

java">public class Test2 {public static void main(String[] args) throws Exception {}static long gcd(long a,long b){return b==0 ? a : gcd(b,a%b);}
}

欧几里得算法的延展-贝祖等式

对任何整数a，b和他们的最大公约数d，关于未知数x，y的线性丢番图方程（裴蜀等式）：ax+by=m，有整数解时，当且仅当m是d的倍数
裴蜀等式有解时必定有无穷个整数解，每组解x、y都称为裴蜀数。
特殊的：ax+by=1，当且仅当a与b互质时才有解
假设现有ax+by=m的一组解x1，y1 那么该方程的其他解为 x=x1+k(b/d) ,b/d为a的变化幅度 ; y=y1-k(a/d) ,a/d为y的变化幅度
例子12x+42y=6 已知一组解为4,-1 -> (4-7,-1+2) =-3,1

问题：求a、b的最大公约数m的同时，求出ax+by=m的一组解
解法；欧几里得算法终止状态为b`=0，此时a`即为最大公约数，此时带入ax+by=m 为 a`x+0=a` ,此时x=1，y为任意数，b为0.
x ,y为上一层递归，x1，y1为新一层递归
现在我们得到了ax+by=m递归若干次后的一组解，即 bx1 +(a%b)y1=m ，现在我们需要该该解返回到递归前
其中 a%b = a - (a/b)*b 其中/为整除（5/2=2，1/3=0）
所以 bx1 + (a%b)y1 = m转换为 m = bx1 +(a-(a/b)*b)y1 = ay1 + b(x1-a/b*y1) 注意：此时 a/b*b != a;
所以我们知道了递归后的y1 = 递归前的x ，递归前的y=递归后的(x1-a/b*y1)

java">public class Test2 {public static void main(String[] args) throws Exception {gcd1(2,7);}static long X =0, Y =0;//求ax+by=d的整数解static long gcd1(long a,long b){if(b==0){X =1;Y =0;System.out.println("最大公约数为："+a);return a;}long ans = gcd1(b,a%b);//更新x，y用于更新上一层的x，ylong temp= X;X = Y;Y =temp-a/b* Y;return ans;}
}

贝祖等式
对任何整数a，b和他们的最大公约数d，关于未知数x，y的线性丢番图方程（裴蜀等式）：ax+by=m，有整数解时，当且仅当m是d的倍数

java">   static long X =0, Y =0;//求ax+by=d的整数解static long gcd1(long a,long b){if(b==0){X =1;Y =0;System.out.println("最大公约数为："+a);return a;}long ans = gcd1(b,a%b);//更新x，y用于更新上一层的x，ylong temp= X;X = Y;Y =temp-a/b* Y;return ans;}static long beiZu(long a, long b, long m) throws Exception {long d = gcd1(a,b);if(m%d!=0)throw new Exception("无解");long n = m/d;X *=n;Y *=n;return d;}

问题：矿车有俩种操作，向前走97m，或向后走127m，需要将矿车停在前方1m处，计算最少需要操作多少次

java">    static void f1(){try {long ans = beiZu(97, -127, 1);System.out.println(Math.abs(X)+Math.abs(Y));} catch (Exception e) {throw new RuntimeException(e);}}

求解线性同余方程

同余方程ax≡b(mod m) 对于未知数x有解，当且仅当b是gcd(a,m)的倍数时才有解。且当方程有解时方程有gcd(a,m)个解
求解ax≡b(mod m)相当于求解ax+my=b（x，y为整数）

问题：俩只青蛙处在一条圆的周长上的俩个不同位置，圆周长为L米，它们想见面，它们同时顺时针跳，圆单位长度为1m，
俩只青蛙A，B的出发点分别在于x，y，一次跳跃距离分别为m米，n米，俩只青蛙跳一次花费时间相同，问最少跳几次后才处于同一点上
测试用例会给定x，y，L，m，n

解法：假设跳k次后相遇，A青蛙总移动距离为x+km ,B青蛙的为y+kn ，满足(x+km)≡(y+kn)(mod L)
(x+km) - (y+kn) = L * t (t为未知数，若干圈) -> x-y +k(m-n) =L * t
k(m-n) - L *t =y-x 带入ax+by=m ，其中k与t是未知数
a = m-n ，b=L，m=y-x

java">    static void f2(long x,long y,long m,long n,long L){ //分别为a的起始位置，b的起始位置，a跳一次距离，b跳一次距离，圆的长度long a =m-n;long b=L;m=y-x;long d = 0;try {d = beiZu(a, b, m);//得到x即俩青蛙各自跳的次数//因为x可能为负数，代表反方向跳，不允许//ax+by=m式中，如果解出x为负数，那么需要将x变为正数，x变化是基于b/d变化的long t = Math.abs(b/d); //t为x每次变化的幅度X=(X%t+t)%t; //x%t的结果一定小于t，如果结果小于0 加t后结果一定在0到t之间；如果结果大于0，加t一定大于t，需要%t才得到最小的正数解System.out.println(X);} catch (Exception e) {System.out.println("出错");}}

模的逆元：

ax≡1(mod m) 即ax%m=1，转换为 ax + my = 1，当且仅当gcd(a,m)=1时有解，这时求出的x为a对模m的乘法逆元。

java">    static long f3(long a,long m) throws Exception {long d = beiZu(a, m, 1);X=(X%m+m)%m;//保证X大于0；return d;}

问题：求(A/B)%9973 ，其中未知的A是大于9973的，但我们已知n=A%9973 和B，且A/B结果为整数。且gcd(B,9973)=1
注意: (A/B)%9973 != (A%9973)/(B%9973)

(A/B)%9973 = A*B对9973的逆元 %9973
将A/B转变为A * (1/B) 因为且gcd(B,9973)=1所以存在x使Bx≡1(mod 9973)成立，令x=1/B，根据模的逆元求出x
所以(A/B)%9973=Ax%9973=(A%9973)*(x%9973)=n*x%9973

java">    static void f4(long n,long B) throws Exception {f3(B, 9973);System.out.println("逆元X="+X);System.out.println(X*n%9973);}

同余方程组
孙子算经中记载有：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问该物几何
设该物为x，x%3=2 ，x%5=3，x%7=2 -> x≡2(mod 3),x≡3(mod 5) x≡2(mod 7)
先合并前俩个式子
x=2+3*y1,x=3+5*y2 -> 3y1-5y2=1 带入贝祖等式，可解出y1，然后把y1带入原式可解出一个特解x0
x的变化与y1与y2有关，而y1的变化幅度是5/（3，5的最大公约数：1），y2的变化幅度是3/（3，5的最大公约数：1）
然后推出x的表达式；x=x0+k*lcm（3，5），加上3和5的公倍数的k倍 ->x≡x0(mod lcm(3,5))
然后在这次得到的新式子联合下一个式子 x=x0+k*lcm（3，5）->x%lcm(3,5)=x0 联合 x%7=2

java">    static long f5(long[] a,long[] m) throws Exception { //m为除的数,模的集合，3，5，7等，a为余数的集合，2，3，2等int len = a.length;if(a.length==0 || a[0]==0)return m[0];for(int i=1;i<len;i++){long d = beiZu(m[i - 1], -m[i], a[i] - a[i - 1]);long x0=a[i-1]+m[i-1]*X;  //得到的X为y1，代入得到上一个同余方程的特解long lcm = m[i-1]*m[i]/d; // 最小公倍数a[i]=(x0%lcm+lcm)%lcm; //将特解x0改为大于0的最小值m[i]=lcm;}return a[len-1]%m[len-1]; //最小的正数解}