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

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

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

java算法实现：

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

或者

private static int getGCD(int a, int b) {//不要求a>bwhile (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.csdn.net/lhfight/article/details/7757057