一、
欧几里德
算法又称辗转相除法，用于计算两个（或者多个）整数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的最小公倍数。即可。
PKU2891：
package D0718;
/*
* 题目大体意思就是求x%ai=ri要求x的最小值
* 中国剩余定理
* 对于同余方程组：
* x=a1 (mod m1)
* x=a2 (mod m2)
* 方程组有一个小于m(m1,m2的最小公倍数）的非负整数解的充要条件是(a1-a2)%gcd(m1,m2)=0,同样利用扩展欧几里得算法。两式联立：a1+m1*y=a2+m2*z
* 则：a1-a2=m2*z-m1*y这样就可以解出z和y,则:x=a2+m2*z
* 而对于一般情形：(设m1,m2,...mk两两互素)时有：
* a=b[1] (mod w[1])
* a=b[2] (mod w[2])
* .....
* a=b[n] (mod w[n])
* 其中w,b已知，w[1],w[2]...w[n]是两两互素的正整数，求a
* 令W=w[1]*w[2]*...w[n]，用W[i]=W/w[i],因为gcd(W[i],w[i])=1,故有；两整数p[i],q[i]满足W[i]*p[i]+w[i]*q[i]=1;如果记e[i]=W[i]*p[i]，那么当j!=i时有:e[i]=0 (mod w[j]),当j=i时有：e[i]=1 (mod w[j]);
* 所以很明显：e[1]*b[1]+e2*b[2]+......e[k]*b[k]就是方程的一个解，加减W倍后就可以得到最小非负整数解了
* 而对于w[1],w[2].....w[n]不互素的情形，就只能两个两个来求了
* x=a[1] (mod m[1])
* x=a[2] (mod m[2])
* 解完后，a=x,m=m1和m2的最小公倍数
* 将题目意思转化为公式：a1*x-a2*y=r2-r1,用欧几里得扩展算法求解
* */
import java.util.Scanner;
public class PKU2891 {
static boolean flag;
static long d, x, y;
static long result;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a1, m1, m2, a2, k;
while (sc.hasNext()) {
k = sc.nextLong();
m1 = sc.nextLong();
a1 = sc.nextLong();
k -= 1;
flag = false;
result = 0;
x = y = 0;
d = 0;
for (int i = 0; i < k; i++) {
m2 = sc.nextLong();
a2 = sc.nextLong();
long b = a2 - a1;
d = extend_GCD(m1, m2);
if (b % d != 0)
flag = true;// 不存在整数解
result = (x * (b / d) % m2 + m2) % m2;
a1 = a1 + m1 * result; // 对于求多个方程
m1 = (m1 * m2) / d; // lcm(m1,m2)最小公倍数；d是m1 和 m2 的最大公约数
a1 = (a1 % m1 + m1) % m1;
}
if (flag)
System.out.println(-1);
else
System.out.println(a1);
}
}
// 扩展的欧几里德
private static long extend_GCD(long a, long b) {
long ret, t;
if (b == 0) {
x = 1;
y = 0;
return a;
}
ret = extend_GCD(b, a % b);
t = x;
x = y;
y = t - (a / b) * y;
return ret;
}
}
推荐题目：pku2115；pku2891；pku1061；pku1006；pku2142；强烈推荐sgu106。
这些题目的解题思路及AC代码（java实现）
pku1061:
http://blog.csdn.net/lhfight/article/details/7757057
PKU2891:
http://blog.csdn.net/lhfight/article/details/7759613
PKU2115:
http://blog.csdn.net/lhfight/article/details/7761779
PKU1006:
http://blog.csdn.net/lhfight/article/details/7763563