扩展欧几里德

扩展欧几里德 1、求解不定方程（ax+by=c,已知x,y,c,求a,b）

2、求解模的线性同余方程（ axΞb(mod m) 对于未知数x的求解）

3、求模的逆元 axΞ1(mod m) 此时的x称为a的对模m乘法的逆元）

1、求解不定方程：

ax+by=c

ax0+by0=gcd(a,b);

ax0*c/gcd(a,b)+by0*c/gcd(a,b)=c;

x=x0*c/gcd(a,b);

y=y0*c/gcd(a,b);

bool linear_equation(int a,int b,int c,int &x,int &y)
{
    int d=exgcd(a,b,x,y);
    if(c%d)
        return false;
    int k=c/d;
    x*=k; y*=k;    //求得的只是其中一组解
    return true;
}

View Code

2、基本算法：存在整数x,y,使得 ax+by=gcd(a,b);

int extgcd(int a,int b,int &x,int &y){
if(b==0){
  x=1;
  y=0;
  return a;
}
int d=extgcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
return d;
}

当b==0时，x=1,y=0,则 gcd(a,b)=a; 此时的a为a，b的最大公约数

ax1+by1=gcd(a,b);

bx2+(a%b)y2=gcd(b,a%b);

gcd(a,b)=gcd(b,a%b);

所以

ax1+by1=bx2+(a%b)y2=bx2+(a-(a/b)*b)y2=bx2+ay2-(a/b)*by2=ay2+b(x2-a/by2)

恒等式

x1=y2;

y1=x2-a/b*y2

前面的x,y基于后面的，所以一直计算，直到最后，x=1，y=0；

再从后往前一次递归出所有的x，y

3、求解模的线性同余方程 axΞb(mod m) 对于未知数x的求解

同余方程 axΞb(mod m) 对于未知数x有解，当且仅当 gcd(a,m)|b。且方程有解时，有gcd（a,m）个

求解 axΞb(mod m) 相当于求解 ax+my=b 设gcd(a,m)=d a0=a/d m0=a/d

则 a0x+m0y=b/d 此时（a0,m0）=1

首先看一个简单的例子：

5x=4(mod3)

解得x = 2,5,8,11,14.......

由此可以发现一个规律，就是解的间隔是3.

那么这个解的间隔是怎么决定的呢？

如果可以设法找到第一个解，并且求出解之间的间隔，那么就可以求出模的线性方程的解集了.

比如

5*2=4（mod 3）

5*5=4 (mod 3)

25-10=15 可以整除 5和3

设间隔为

那么有

a*x = b(mod m);

a*(x+dx) = b(mod m);

两式相减，得到:

a*dx(mod m)= 0;

a*dx 是a和m的公倍数，如果找到最小公倍数，则找到对应的最小dx

设a,m的最大公约数为 d 最小公倍数为 a*m/d

则对应的最小dx=m/d,这样间隔就有了，再找到第一个解

如何找第一个解？

ax+my=b gcd(a,m)=d

满足欧几里德方程：

ax0+my0=d;

两边同时乘以 b/d

ax0*b/d+my0*b/d=b;

所以 x= x0* b/ d 为 ax= b (mod m ) 的解。

调用 extgcd(a,b,x,y)

x*(b/d)%m 为第一个解

第一个解加上间隔，在小于等于d的循环里依次计算即可

bool modular_linear_equation(int a,int b,int n)
{
    int x,y,x0,i;
    int d=exgcd(a,n,x,y);
    if(b%d)
        return false;
    x0=x*(b/d)%n;   //特解
    for(i=1;i<d;i++)
        printf("%d
",(x0+i*(n/d))%n);
    return true;
}

View Code

4、计算逆元

axΞ1(mod m)

相当于 ax+my=1 有唯一解利用扩展欧几里德求出x即可