欧几里得算法和扩展欧几里得算法数论基础

r囧r小猫 2021-12-12 07:19 341阅读 0赞

这两个算法可以说是OI里数学模块最重要的基础了（如果位运算不算数学的话）。

**一.欧几里得算法（Euclidean Algorithm）**

模板水题：**[LOJ P1212][]**　　（LOJ真是个好东西啊）

在学习一种算法前，我认为我们首先应该知道，这种算法是要解决什么问题的。

小学就已经学过了两个数的最大公约数，而欧几里得算法就是为了求出两个数a、b的最大公约数的，这个最大公约数可以表示为gcd(a,b)。

欧几里得算法又称**辗转相除法**，这个名字已经揭示了它的主要思想：辗转相除！

它的函数代码只有一行，简单便捷，复杂度O(log n)：

int gcd(int a,int b){ return b?gcd(b,a%b):a; }

不要小看这短短的一行代码，其中蕴含了无尽的人生智慧（/滑稽）

因为代码很短，所以算法的过程我就不赘述了，主要就是递归，可以从代码中看出来。

如果赶时间（比如距离noip就差一天了），可以忽略掉证明只记代码，但是我认为证明还是必要的，证明在这里：**[证明][Link 1]**

** **

**二.扩展欧几里得算法**

首先我们要理解一个定理：

> 　　　　**贝祖定理**：若存在a、b是整数，则必存在整数x、y，满足ax+by=gcd(a,b)。

证明在这里写得比较清楚：**[证明][Link 2]**

**　　**需要耐心理解。

> 　　贝祖定理  
> 
> 
> 　　证明：
> 
> 　　　　当 b=0 时，gcd(a,b)=a，此时 x=1 , y=0
> 
> 　　　　当 b!=0 时，
> 
> 　　　　　　设 ax1\+by1=gcd(a,b)=gcd(b,a%b)=bx2\+(a%b)y2
> 
> 　　　　　　又因 a%b=a-a/b\*b
> 
> 　　　　　　则 ax1\+by1=bx2\+(a-a/b\*b)y2
> 
> 　　　　　　　　  ax1\+by1=bx2\+ay2\-a/b\*by2
> 
> 　　　　　　　　　　 =ay2\+**b**x2\-**b**\*a/b\*y2
> 
> 　　　　　　　　　　 =ay2\+**b**(x2\-a/b\*y2)
> 
> 　　　　　　解得 x1=y2 , y1=x2-a/b\*y2
> 
> 　　　　因为当 b=0 时存在 x , y 为最后一组解
> 
> 　　　　而每一组的解可根据后一组得到
> 
> 　　　　所以第一组的解 x , y 必然存在
> 
> 　　　　证毕。

显然，因为当b=0时，x=1，y=0，这时x和y是已知的，所以我们很容易想到通过递归来求解。

不断返回下一层的解，来得到这一层的解，最终回溯回来，得解。

因为是借助欧几里得算法进行回溯的，所以复杂度也是O(log n)。

基本理解扩展欧几里得算法后，我们就可以来看看例题了。

例题：**[洛谷oj P1082][oj P1082]**

同余定理：给定一个正整数$m$，如果两个整数$a$和$b$满足$a-b$能够被$m$整除，即$(a-b)/m$得到一个整数，那么就称整数$a$与$b$对模$m$同余，记作$a\\ ≡\\ b\\ (\\ mod \\ m \\ )$。对模$m$同余是整数的一个等价关系。

其实就是$a\\ mod\\ m\\ =\\ b\\ mod\\ m$。

当$b>=1$时，因为$1\\ mod\\ b\\ =\\ 1$，所以$ax\\ ≡\\ 1(mod b)$就是$ax mod b=1$。其实就差不多是方程$ax\\ +by\\ =\\ 1$，y可能为负数，所以我们在做exgcd后还要加个答案处理。

ac代码：

#include <cstdio>
    using namespace std;
    
    long long a,b;
    
    long long x,y;
    inline void exgcd(long long a,long long b){
        if (b==0){
            x=1,y=0;
            return ;
        }
        else exgcd(b,a%b);
        long long x1=x;
        x=y,y=x1-a/b*y;
        return ;
    }
    
    int main(){
        scanf("%lld%lld",&a,&b);
        exgcd(a,b);
        while (x<0)
            x+=b;
        x%=b;
        printf("%lld",x);
        return 0;
    }

转载于:https://www.cnblogs.com/awakening-orz/p/10896923.html

[LOJ P1212]: http://codevs.cn/problem/1212/
[Link 1]: http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html
[Link 2]: https://www.cnblogs.com/hadilo/p/5914302.html
[oj P1082]: https://www.luogu.org/problemnew/show/P1082