- 计算最大公约数和不定方程
- 计算同余方程和同余方程组
- 计算多项式同余方程
计算最大公约数常用有辗转相除法或者是欧几里得算法。二者原理基本相似：整数a和整数b的最大公约数通过反复应用除运算，直到余数为零，最后的非零余数就是最大公约数。 1.欧几里得算法(辗转相除法)如下：
void gcd(int a,int b)
{
if(b==0)
return a;
else return gcd(b,a%b);
}
欧几里得算法数学证明： 欧几里得有个非常强的定理，即gcd(a,b)=gcd(b,a mod b)，让我们来证明一下（mod 是取余，gcd是最大公约数，| 是能整除） 假设a、b的公约数为k，a = bx + y 则 k | a，k | b，a mod b=y 因为 k | b，所以 k |bx，又因为 k | a，所以 k | (a - bx)，即 k | y 而a mod b = y，所以 k | a mod b 再假设b、a mod b的公约数为kk，同理得 kk | a，所以（a，b）和（b，a mod b）的公约数是相同的，所以它们的最大公约数也是相同的 所以gcd(a,b)=gcd(b,a mod b) 时间复杂度O(log n) (讨论情况为a>=b） a mod b必然是小于a/2的，而上一次的b会变成下一次的a，上一次的a mod b会变成下一次的b，最坏情况也就是b在a/2附近，即a mod b在a/2附近。在最坏情况时每次的值也会减少一半，所以说时间复杂度是O（log n）的。（实际中往往会更低）
欧几里得算法扩展应用乘法逆元： 若有 a*x ≡ 1 （mod m），则称 x 为a关于m的乘法逆元，等价式 a * x+m * y = 1。相当于一个二元一次方程 如何求解 （以下讨论a>b） 显然当 b=0，gcd（a，b）=a。此时 x=1，y=0； 当a>b>0 时 设 ax1+ by1= gcd（a，b）； bx2+ （a mod b）y2= gcd（b，a mod b）； 根据欧几里德原理有 gcd（a，b） = gcd（b，a mod b）； 则：ax1+ by1= bx2+ （a mod b）y2； 即：ax1+ by1= bx2+ （a - [a / b] * b）y2 = ay2+ bx2- [a / b] * by2；（a mod b = a - [a / b]*b；[a / b]代表a整除b） 也就是ax1+ by1 = ay2 + b（x2- [a / b] *y2）； 根据恒等定理得：x1=y2；y1=x2- [a / b] *y2； 这样我们就得到了求解 x1，y1 的方法：x1，y1 的值基于 x2，y2 由引理我们知道：ax+by = z，z为gcd（a，b）若干倍，所以我们先求解ax+by = gcd（a，b），再将求出的解乘以 z/gcd（a，b）就好了。
扩展欧几里得算法代码：
void exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int tmp=exgcd(b,a%b,x,y);
tmp=x;
x=y;
y=tmp-a/b*y;
return r;
}
扩欧算法可用来求解二元一次方程通解（最小）
2.更相减损方法：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。 算法代码
int gcd(int m,int n)
{
int i=0,temp,x;
while(m%2==0 && n%2==0) //判断m和n能被多少个2整除
{
m/=2;
n/=2;
i+=1;
}
if(mx)?n:x;
n=(nn)?m:n; ///采种条件运算表达式求出两个数中的最小值
while(temp>0)
{
if (m%temp==0&&n%temp==0) //只要找到一个数能同时被a,b所整除，则中止循环
break;
temp--; //如不满足if条件则变量自减，直到能被a,b所整除
}
return temp; //返回最大公因数
}
以上为三种求解最大公约数的方法，同余方程和不定方程后期赘述。
