扩展欧几里得算法

扩展欧几里得算法是啥，那就要先知道什么是欧几里得算法

欧几里得算法

扩展欧几里得算法是欧几里得算法的推广，利用欧几里得算法的思想和递归求得贝祖等式a*x+b*y=gcd(a,b)不定方程中的一组x和y的解。

原理如下：

设a>b

1. 当b=0时，很显然a*x=gcd(a,b)=a，所以x=1，而y为任意数，为了同一和方便我们令y=0；
2. 当a>b>0时，设有两组等式a*x1+b*y1=gcd(a,b)，b*x2+(a%b)*y2=gcd(b,a%b)。根据欧几里得算法的递归思想，a和b的gcd为t，而a=q*b+r，r=a-q*b为a，b的线性组合，又因为a%t=0，b%t=0，所以线性组合r%t=0，又有r=a%b，所以gcd(a,b)=gcd(b,a%b)。

联立等式有a*x1+b*y1=b*x2+(a%b)*y2，又有a%b=a-floor(a/b)*b[这里面floor()是向下取整的意思]，

即：ax1+by1=bx2+[a-floor(a/b)*b]*y2，我们将a，b视为未知数所以由x1*a+y1*b=y2*a+[x2-floor(a/b)*y2]*b可得

x1=y2

y1=[x2-floor(a/b)*y2]

这样我们就找到了扩展欧几里得的递归算法了

总结一下

欧几里得算法的递归求最大公约数是通过递归知道m=q*t+0，在下一次递归时余数r=0，递归结束，在扩展欧几里得算

法中同样是递归当b=0时递归结束，又有原理中情况1，b=0，则x=1，y=0；

void Ex_gcd(int a, int b, int &x, int &y)
{
    if(b == 0)//递归出口
    {
        x = 1;
        y = 0;
        return;
    }
    int x1, y1;
    Ex_gcd(b, a%b, x1, y1);
    x = y1;
    y = x1-(a/b)*y1;
}

上述是求得一组x0，y0解利用这个组求通解怎么求呢？

有a(x0+n*b)+b*(y0-n*a)=gcd(a,b)

所以x=x0+n*b时n(…，-2，-1，0，1，2，…)，x就是方程的解系了，对应每一个x都应该有一个y与其相对，实际求解

时先不考虑y，当x求出时，将x带回方程求得y即可

当这里的x就包含了所有的解嘛？

显然不是得，我们将原方程两边同除于gcd(a,b),设a1=a/gcd(a,b),b1=b/gcd(a,b)

a1x+b1y=1，与原方程为同解，此时

x=x0+n*b1

又知b1=b/gcd(a,b)<=b，所以这里的x比原x包含更多的解

求最小正数解

while(x<0)
x+=b1;

求解一般线性方程

对于一般的线性方程ax+by=m，我们怎么来求解呢

首先要判断这个方程是否有解，若m%gcd(a,b)==0则方程是有解的，证明如下：已知a%gcd(a,b)=0，b%gcd(a,b)=0，则a，b的线性组合(a*x+b*y)%gcd(a,b)=0，即m%gcd(a,b)=0，证毕

求解方法：

设a1=a/gcd(a,b)，b1=b/gcd(a,b)，m1=m/gcd(a,b)

①a1*x+b1*y=m1与原方程通解，那么当先求得②a1*x+b1*y=1(a1，b1互质，gcd(a1,b1)=1)的一组解x0，y0，则x=x0*m1，y=y0*m1，即x0=x/m1，y0=y/m1代入②式中化简即为①式，故求解一般的线性方程ax+by=m时，先用扩展欧几里得算法求得x0即可，x=x0*m1

d=gcd(a,b);
            a=a/d;
            b=b/d;
            c=c/d;
            Ex_gcd(a,b,x,y);
            x=x*c;

扩展欧几里得的应用——求解逆元

当遇到a/b%m时如何求解呢，对于除法没有取模运算

逆元的概念就是(a*_a)%m=1，中_a就是a的乘法逆元，它等价除法，即a/b%m=a*_b%m

(a*_a)%m=1等价于表达式a*x+m*y=1，之后利用扩展欧几里得算法求解的x0

最小正整数逆元就为x=(x0%m+m)%m[根据同解系可知]

那么当m为负数怎么办呢

用算法使m=-m即可，一句话m=abs(m)，a，b，同理

附上hdu一道求逆元的题

http://acm.hdu.edu.cn/showproblem.php?pid=1576

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
using namespace std;
void Ex_gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    int x1,y1;
        Ex_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int x,y;
        Ex_gcd(b,9973,x,y);
        x=(x+9973)%9973;
        printf("%d\n",(a%9973*x%9973)%9973);
    }
    return 0;
}