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

落日映苍穹つ 2021-12-23 23:55 397阅读 0赞

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

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

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

代码如下

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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;
    }

**然而，你以为这样就完了吗？**

**别高兴的太早，我们上面的方程只是求的ax+by=gcd(a,b)的一组特殊解**

**但往往恶心的出题人会让你求诸如ax+by=c的特殊情况**

**所以仅仅有一个扩展欧几里得是不够的**

我们现在就以Noip提高组2012年的"同余方程"为例

题目见洛谷P1082

其实也是一道扩展欧几里得的模板题

但他是让我们求关于**xx的同余方程ax≡1(mod b) 的最小正整数解。**

还是我们先求出ax+by=gcd(a,b)的解，用裸的扩展欧几里得即可

然后这个同余方程可以看做ax+by=1;

好吧是我看错了

题目中的数据都是满足互质的情况，所以gcd(a,b)一定是1。

那我们怎样来找它的最小整数解呢

那么**取模**就非常重要了！

取模就是将一个随机的值摸到相应的一个区间中

所以说我们求他的最小整数解就可以用这样一个公式来解决

**ans=(x\*(c/gcd(a,b))%abs(b/gcd(a,b))+abs(b/gcd(a,b)))%gcd(b/gcd(a,b))**

转载于:https://www.cnblogs.com/LJB666/p/10502166.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/3411672966f5493ba21a9a3e8f41f300.png