欧几里得算法
欧几里得算法是用来求解两个不全为0的非负整数m和n的最大公约数的一个高效且简单的算法。该算法来自于欧几里得的《几何原本》。数学公式表达如下：
代码语言：javascript复制对两个不全为0的非负整数不断应用此式：gcd(m,n)=gcd(n,m mod n);直到m mod n为0时。m就是最大公约数证明：我们假设有a,b两个不全为0的数，令 a % b = r； 那么有 a = kb r. 假设a,b的公约数是d。记做 d|a,d|b，表示d整除a和b。r = a - kb; 给这个式子两边同除以 d,有 r/d = a /d - kb / d，由于d是a ,b的公约数，那么r/d 必将能整除，即：b 和 a%b的公约数也是d。故：gcd(a,b) = gcd(b, a % b)。到此为止，已经证明了a和b的公约数和 b 和 a % b的公约数相等。直到a mod b为0的时候（因为即使 b > a,经过 a % b后，就变成计算gcd(b,a)。因此，a mod b的值会一直变小，最终会变成0），此时gcd(m,0) = m。因为0除以任何数都是0，所以m是gcd(m,0)的最大公约数。根据上面已经证明的等式gcd(a,b) = gcd(b, a % b)。可得：m就是最大公约数。定理得证。
下面是C 代码实现欧几里得算法。
代码语言：javascript复制#include <iostream>
using namespace std;
int gcd(int m, int n);
int main()
{
int m, n;
cout << "请输入要计算的两个数，用空格隔开:n";
cin >> m >> n;
cout << "最大公约数是：" << gcd(m, n);
return 0;
}
int gcd(int m, int n)
{
int r;
while (0 != n)
{
r = m % n;
m = n;
n = r;
}
return m;
}扩展欧几里得算法
欧几里得算法提供了一种快速计算最大公约数的方法。而扩展欧几里得算法不仅能够求出其最大公约数。而且能够求出m,n和其最大公约数构成的不定方程mx ny=d的两个整数x,y(这里x和y不一定为正数)。
在欧几里得算法中，终止状态是n == 0时，这时候其实就是gcd(m,0)；我们想从这个最终状态反推出刚开始的状态。由欧几里得算法可知。gcd(m,n) = gcd(n,m mod n);那么有如下表达式：
gcd(m,n) = m*x1 n*y1;
gcd(n,m mod n) = n*x2 (m - m/n*n)*y2；（此处的m/n表示整除，例如：6/4 = 1；所以：m mod n = m % n = m - m/n*n）
化简上式有：n*x2 m * y2 - m/n*n*y2
= m*y2 n*(x2 - m/n*y2)
与原式 gcd(m,n) = m*x1 n*y1;对比，容易得出：
x1 = y2;
y1 = x2 - m/n*y2;
根据上面的递归式和欧几里得算法的终止条件n == 0,我们可以很容易知道最终状态是m * x1 0 * y1 = m;故：x1 = 1;根据上述的递推公式和最终状态，可以写出代码如下：
代码语言：javascript复制#include<iostream>
using namespace std;
int exgcd(int m, int n, int &x, int &y);
int main()
{
int x, y;
int m, n;
int gcd;
cout << "请输入两个数字：n";
cin >> m >> n;
cout << "满足贝祖等式" << m << "*x " << n << "*y = " << (gcd = exgcd(m, n, x, y)) << endl;
cout << "最大公约数是：" << gcd << endl;
cout << "其中一组解是：x = " << x << "; y = " << y << endl;
system("pause");
return 0;
}
int exgcd(int m, int n, int &x, int &y)
{
if (0 == n) //递归终止条件
{
x = 1;
y = 0;
return m;
}
int gcd = exgcd(n, m%n, x, y); //递归求解最大公约数。
int temp = x;
x = y; //回溯表达式1：x1 = y2;
y = temp - m / n * y; //回溯表达式2：y1 = x1 - m/n * y2;
return gcd;
}上述的方程m*x n*y=gcd(m,n)；这个方程也被称之为“贝祖等式”。它说明了对a，b和它们的最大公约数d之间的线性丢番图方程。一定存在整数x,y使得m*x n*y=gcd(m,n)成立。从这里也可以得出一个重要推论：
a,b互质的充要条件是方程ax by = 1必有整数解。
现在来讨论一个更一般的方程：ax by = c(a,b,c都是整数)。这个方程想要有整数解，那么根据扩展欧几里得算法我们知道，当且仅当m是d = gcd(a,b)的倍数时有解。同时有无穷多组整数解。
我们知道了线性丢番图方程ax by = c有整数解的条件，并且根据上述算法，也能求出一组丢番图方程的解。但是这组解很可能包含负数。我们通常的需求是最小的特解。也就是这个不定方程的最小正整数解。
一般扩展欧几里得算法有如下应用：
求解乘法逆元
把a*x=1 （ mod p）称为a关于 1 mod p的乘法逆元。 它的解其实就相当于寻找方程 a*x p*y=1 的解。根据乘法逆元的性质，只有当a与p互素，a关于模p的乘法逆元有解。如果时不互素，则无解。那么这个方程就是a,b互质的充要条件是方程ax by = 1必有整数解。我们就可以使用扩展欧几里得算法求得其逆元。
代码语言：javascript复制int inv(int m, int n, int & x, int & y)
{
int gcd = exgcd(m, n, x, y);
if (1 != gcd) //说明乘法逆元不存在
{
return -1;
}
else
{
return (x n) % n; //为了使余数一定为正数
//模运算系统的特性
}
}这样就能求出两个互质的数的逆元了。
最小正整数解
设整数a,b,c；若方程ax by = c的一组整数解为（x0,y0）;那么它的任意组整数解都可以写成：（x0 kb',y0-ka'）.
其中a' = a / gcd(a,b)；b' = b / gcd(a,b);k取整数即可。
代码语言：javascript复制int res(int a, int b, int c ,int &x, int &y)
{
int gcd = exgcd(a, b, x, y); //求出最大公约数以及满足等式mx ny=gcd(m,n)的一组(x,y);
if (0 != c % gcd) //如果c不是gcd(m,n)的倍数，该丢番图方程无整数解。
{
return -1;
}
x *= c / gcd; //将x转化为方程ax by=c的解。
//先求出x的最小值。根据通解公式x = x0 kb'; b'= b / gcd(a,b);
b /= gcd; //求b'
if (b < 0)
{
b = -b; //b为负数，则取绝对值
}
int r = x % b; //求出最小整数解
if (r <= 0)
{
r = b; //求出最小正整数解
}
return r;
}
