数论杂谈——欧几里得算法及扩展欧几里得-蒲公英云

数论杂谈——欧几里得算法及扩展欧几里得

数学是oi的重要基础，所以说数论在oi中占据了非常重要的地位，因此，学好数学，对于一个oier来说也是非常重要的。

oi中的数学，其实也就和数竞并没有什么区别。

欧几里得法辗转相除法求最大公约数我们可以证明gcd(a,b)=gcd(b,a%b)，也就是我国古代数学智慧的结晶，更相损减术。并且一直递归下去，直到b的值为零，最大公约数值即为a。在这里就不给出详细证明了，大家可以代几个数据去验证它一下。谁叫我数学太菜。

代码如下

int GCD(int a,int b)
{
    if(!b)
    {
        return a;
    }
    else
    {
        return (b,a%b);
     }
}

其实讲了这么多，我们还是为了引出扩展欧几里得算法，也是基于辗转相除法的基础，对此我们就可以求得不定方程ax+by=gcd(a,b)的一组特殊解。

这个方程也可以等价于ax≡gcd(a,b)(mod b)也就是我们所说的同余方程。

我们还可以通过此得出一种性质，那就是bx’+a%by’=gcd(b,a%b)=ax+by=gcd(a,b)。也就和辗转相除法联系起来了。

所以我们再把a%b展开，就可以得到a%b=a-a/b，再把它代入原式得bx’+(a-a/b)y’=bx’+ay’-a/b*y’=ay’+bx’-a/b*y。我们可以发现，在原来的位置上(ax+by)，可以等效于x=y’,y=x-(a/b*y)。因此我们只要知道一个解便可以推出。

代码如下

int Exgcd(int a,int &x,int b,int &y)//‘&’符号便于我们直接修改x和y的值
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;//相当于求一个gcd的过程
    }
    int ans=Exgcd(b,x,a%b,y);//求解方程
    int tmp;//用来保存上一个x的值
    x=y;
    y=tmp-(a/b)*y;//我们刚才推出的式子
    return ans;
}