扩展欧几里得算法

扩展欧几里得算法

用途

当我们已知a,b

扩展欧几里得算法可以求出满足a*x+b*y=GCD(a,b)的(x,y)解集

GCD(a,b)表示a,b的最大公约数

前导知识

GCD(a,b)=GCD(b,a\%b)

GCD(a,0)=0

a\%b=a-a/b*b

推导过程

其实扩展欧几里得的推导过程挺自然的

a*x+b*y

=GCD(a,b)

=GCD(b,a\%b)

=b*x+(a\%b)*y

=b*x+(a-a/b*b)*y

=b*x+a*y-a/b*b*y

=a*y+b*x-a/b*b*y

=a*y+(x-y*a/b)*b

这样不断的递归下去

当b=0时

x=1,y=0

代码

注意：

我们在求(x-y*a/b)的时候需要用到上一层的x

但此时上一层x已经被赋值成了y

所以我们需要开一个中间变量来记录上一层的x

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y),tmp;
    tmp=x,x=y,y=tmp-a/b*y;
    return r;
}

应用

1

扩展欧几里得最重要的应用就是求形如a*x+b*y=c的解

那么如何求呢？

首先，这个方程能够能力的条件是c\%GCD(a,b)=0，这个应该比较显然

根据前面将的扩展欧几里得算法

我们可以先求出a*x_0+b*y_0=GCD(a,b)的解x_0,y_0

然后方程两边同时除以GCD(a,b)

就得到a*x_0/GCD(a,b)+b*y_0/GCD(a,b)=1的解

再在方程两边同乘c

就得到了方程

a*x_0/GCD(a,b)*c+b*y_0/GCD(a,b)*c=c

是不是很简单？

2

若GCD(a,b)=1，且x0,y0为a*x+b*y=c的一组解，则该方程的任一一解可以表示为

x=x_0+b*t,y=y_0-a*t

证明:

a*x+b*y

=a*(x_0+b*t)+b*(y_0-a*t)

=a*x_0+a*b*t+b*y_0-a*b*t

=a*x_0+b*y_0

例题

洛谷P1516 青蛙的约会

根据题目要求列出等式，化简即可

题解