您的位置: 首页  >  IT文章  >  欧几里得+扩充的欧几里得算法+线性同余方程+中国剩余定理

欧几里得+扩充的欧几里得算法+线性同余方程+中国剩余定理

分类: IT文章 • 2022-08-31 12:39:31
欧几里得+扩展的欧几里得算法+线性同余方程+中国剩余定理

一、欧几里德算法又称辗转相除法，用于计算两个（或者多个）整数a，b的最大公约数。

这个比较简单，不啰嗦了！！！

java算法实现：

// 计算最大公约数
	private static int getGCD(int a, int b) {//注意a>b
		if (a % b == 0)
			return b;
		else
			return getGCD(a, a % b);
	}

或者

private static int getGCD(int a, int b) {//不要求a>b
		while (b != 0) {
			int k = b;
			b = a % b;
			a = k;
		}
		return a;

	}

欧几里得算法比较简单，就不举具体例子了吧！！！

 

二、扩展的欧几里德定理：

       对于不完全为 0 的非负整数 a和b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
java 算法实现：
private static int extend_getGCD(int a, int b, int x, int y) {
		int temp,ans;
		if (b == 0) {
			x = 1;
			y = 0;
			return a;
		}
                  ans = extend_getGCD(b, a%b, x, y); 
		temp = x;
		x = y;
		y = temp - a / b * y;
		return ans;
 	}
把这个实现和Gcd的递归实现相比，发现多了下面的x,y赋值过程，这就是扩展欧几里德算法的精髓。
　　我们可以这样思考:
　　对于a' = b, b' = a % b而言，我们求得x, y使得a'x + b'y = Gcd(a', b')
　　由于b' = a % b = a - a / b * b (注：这里的/是程序设计语言中的除法)
　　那么可以得到:
　　a'x + b'y = Gcd(a', b') ===>
　　bx + (a - a / b * b)y = Gcd(a', b') = Gcd(a, b) ===>
　　ay +b(x - a / b*y) = Gcd(a, b)
　　因此对于a和b而言，他们的相对应的p，q分别是y和(x-a/b*y)。
扩展的欧几里德应用：PKU1061
package D0717;

/*
 * 扩展的欧几里德算法解线性同余方程
 * 根据扩展的欧几里德gcd(a,b)=A*a+B*b一定存在整数A、B使等式成立。
 * 所以，当我们将式上式化简成：
 * (x+s*m)-(y+s*n)=k*L  --------k=(0,1,2,3,4...)
 * ===>(m-n)*s-k*L=x-y
 * 令m-n = a; x-y = c
 * 则=====>a*s-k*L = c, 这时候，根据欧几里德算法，如果C是 gcd(a,b)的整数倍，则肯定有S、K肯定有整数解(即能见面)。
 * 相反，则可以直接判断两只青蛙不能见面。
 * 拓展欧几里德算法是在有整数解的基础上，用来求解所有可能的S、K
 * */
import java.util.Scanner;

public class PKU1061 {
	static long X, Y;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x, y, m, n, l, a, b, c;
		while (sc.hasNext()) {
			x = sc.nextLong();
			y = sc.nextLong();
			m = sc.nextLong();
			n = sc.nextLong();
			l = sc.nextLong();
			a = n - m;
			b = l;
			c = x - y;
			if (a < 0) {
				a = -a;
				c = -c;
			}
			long gcd = extend_GCD(a, b);
			if (m == n || c % gcd != 0)// c不是gcd（a，b）的整数倍，直接得出结论：不能相遇
				System.out.println("Impossible");
			else {
				System.out.println((c-b*Y)/a);
				b /= gcd;
				c /= gcd;
				long t = c * X;
				System.out.println((t % b + b) % b);
			}
		}

	}

	// 扩展的欧几里得
	private static long extend_GCD(long a, long b) {
		long temp, ret;
		if (b == 0) {
			X = 1;
			Y = 0;
			return a;
		} else {
			ret = extend_GCD(b, a % b);
			temp = X;
			X = Y;
			Y = temp - (a / b) * Y;
			return ret;
		}
	}

}


三、线性同余方程：
       在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：
　　ax≡b (mod n)或者a*x+b*y=n 的方程。
 
      对于方程 a*x+b*y=n；有整数解得充分必要条件是（n %（a，b）==0）即n能够被a和b的最大公约数整除（n=gcd(a,b)*倍数）记作gcd(a,b)|n，其实就是扩展的欧几里得定理。

     所以方程 a*x+b*y=n；我们可以先用扩展欧几里德算法求出一组x0，y0。也就是a*x0+b*y0=gcd（a，b）；然后两边同时除以gcd（a，b），再乘以n。这样就得到了方程a*x0*n/（a，b）+b*y0*n/（a，b）=n；我们也就找到了方程的一个解。

     还有一个定理：若gcd（a，b）=1，且x0，y0为a*x+b*y=n的一组解，则该方程的任一解可表示为：x=x0+b*t，y=y0-a*t；且对任一整数t，皆成立。（这个大家记住就可以了）

     这样我们就可以求出方程的所有解了，但实际问题中，我们往往被要求去求最小整数解，所以我们就可以将一个特解x，t=b/gcd（a，b），x=(x%t+t）%t；就可以了。

 

四、中国剩余定理（方程组的情形）

中国剩余定理：

•今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

 

对于同余方程组：

      x=a1 （mod m1）；   1

      x=a2 （mod m2）；    2

      方程组有一个小于m（m1，m2的最小公倍数）的非负整数解的充分必要条件是（a1-a2）%（m1，m2）==0 ，同样利用扩展欧几里德算法。

      两式联立：a1+m1*y=a2+m2*z。

      则：a1-a2=m2*z-m1*y; 这样就可以了解出z和y，则：x=a2+m2*z；  

      现在我们将其推广到一般情形：（设m1,m2,···,mk两两互素）

      x=a1（mod m1）;

     x=a2（mod m2）;

      ···

      x=ak（mod mk）;其在M=m1*m2*···*mk;中有唯一整数解。

      记Mi=M/mi;因为（Mi,mi）=1,故有两整数pi,qi满足Mi*pi+mi*qi=1，如果记ei=Mi*pi;那么：ei=0 （mod mj）,j!=i; ei=1（mod mj）,j=i;

      很明显，e1*a1+e2*a2+···+ek*ak就是方程的一个解，加减M倍后就可以得到最小非负整数解了。

      如果m1,m2,···,mk不互素，那只能两个两个求了。

      x=a1 （mod m1）；  

      x=a2 （mod m2）；   

      解完后，a=x； m=m1和m2的最小公倍数。即可。

      推荐题目：pku2115；pku2891；pku1061；pku1006；pku2142；强烈推荐sgu106。

这些题目的实现过程我会在后面贴出来。

pku1061:http://blog.****.net/lhfight/article/details/7757057

相关推荐