一。欧几里得算法
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。
基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。
递归实现：
1 int gcd(int a,int b)2 {3 if(b==0)4 return a;5 return 6 gcd(b,a%b);7 } 优化
1 int gcd(int a,int b)2 {3 if(b==0)4 return a;5 return 6 gcd(b,a%b);7 } 迭代实现
1 int Gcd(int a, int b) 2 { 3 while(b != 0) 4 { 5 int r = b; 6 b = a % b; 7 a = r; 8 } 9 return a;10 } 二.扩展欧几里德算法
基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
我们观察到：欧几里德算法停止的状态是： a= gcd ， b = 0 ，那么，这是否能给我们求解 x y 提供一种思路呢？因为，这时候，只要 a = gcd 的系数是 1 ，那么只要 b 的系数是 0 或者其他值（无所谓是多少，反正任何数乘以 0 都等于 0 但是a 的系数一定要是 1），这时，我们就会有： a*1 + b*0 = gcd
当然这是最终状态，但是我们是否可以从最终状态反推到最初的状态呢？
假设当前我们要处理的是求出 a 和 b的最大公约数，并求出 x 和 y 使得 a*x + b*y= gcd ，而我们已经求出了下一个状态：b 和 a%b 的最大公约数，并且求出了一组x1 和y1 使得： b*x1 + (a%b)*y1 = gcd ， 那么这两个相邻的状态之间是否存在一种关系呢？
我们知道： 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)
对比之前我们的状态：求一组 x 和 y 使得：a*x + b*y = gcd ，是否发现了什么？
这里：
x = y1
y = x1 – a/b*y1
以上就是扩展欧几里德算法的全部过程，依然用递归写：
1 int exgcd(int a,int b,int &x,int &y) 2 { 3 if(b==0) 4 { 5 x=1; 6 y=0; 7 return a; 8 } 9 int ans=exgcd(b,a%b,x,y);10 int t=x;11 x=y;12 y=t-a/b*y;13 return ans;14 } 这就是理论部分，欧几里德算法部分我们好像只能用来求解最大公约数，但是扩展欧几里德算法就不同了，我们既可以求出最大公约数，还可以顺带求解出使得：
a*x + b*y = gcd 的通解 x 和 y
扩展欧几里德算法的应用主要有以下三方面：
（1）求解不定方程；
（2）求解模线性方程（线性同余方程）；
（3）求解模的逆元；
其中扩展欧几里得算法一个重要的应用在求解形如 a*x +b*y = c 的特解，比如一个数对于另一个数的乘法逆元
三。乘法逆元
什么叫乘法逆元？
这里，我们称 x 是 a 关于 m 的乘法逆元
这怎么求？这里我们利用扩展欧几里得算法，等价为： a*x + m*y = 1
我们发现当gcd(a , m) != 1 的时候是没有解的，这也是 a*x + b*y = c 有解的充要条件： c % gcd(a , b) == 0
一般，我们能够找到无数组解满足条件，但是一般是让你求解出最小的那组解，怎么做？我们求解出来了一个特殊的解 x0 那么，我们用 x0 % m其实就得到了最小的解了。为什么？
可以这样思考：
x 的通解不是 x0 + m*t 吗？
那么，也就是说， a 关于 m 的逆元是一个关于 m 同余的，那么根据最小整数原理，一定存在一个最小的正整数，它是 a 关于m 的逆元，而最小的肯定是在（0 , m）之间的，而且只有一个，这就好解释了。
但是，由于问题的特殊性，有时候我们得到的特解 x0 是一个负数，还有的时候我们的 m 也是一个负数这怎么办？
当 m 是负数的时候，我们取 m 的绝对值就行了，当 x0 是负数的时候，x0% m 的结果仍然是负数（在计算机计算的结果上是这样的，虽然定义的时候不是这样的），这时候，我们仍然让 x0 对abs(m) 取模，然后结果再加上abs(m) 就行了，于是，我们不难写出下面的代码求解一个数 a 对于另一个数 m 的乘法逆元：
1 int cal(int a,int m) 2 { 3 int x,y,ans,gcd; 4 gcd=exgcd(a,m,x,y); 5 if(1%gcd!=0)///无解 6 { 7 return -1; 8 } 9 x=x*1/gcd;10 m=abs(m);11 ans=x%m;12 if(ans<=0)13 {14 ans=ans+m;15 }16 return ans;17 }
这里给出一道例题作为乘法逆元的模板
给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。
输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)
Output
输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。
Sample Input
2 3
Sample Output
2
1 #include2 #include 3 using namespace std; 4 void exgcd(int a,int b,int &x,int &y) 5 { 6 if(b==0)///递归结束条件 7 { 8 x=1; 9 y=0;10 return ;11 }12 exgcd(b,a%b,x,y);13 int t=x;14 x=y;15 y=t-a/b*y;16 }17 18 int main()19 {20 int n,m;21 int x,y;22 scanf("%d%d", &m,&n);23 exgcd(m,n,x,y);24 while(x<0)25 {26 x=x+n;27 }28 printf("%d\n",x);29 return 0;30 }