裴蜀定理 && 扩展欧几里得算法求逆元详解

裴蜀定理 ：

有一个线性不定方程 ax+by=c

若此方程有解，那么 c=k*gcd(a,b) ，k 为任意正整数

证明：

以下 gcd(a,b) 简称 gcd

 (ax+by) mod gcd=0

又 c mod gcd=0

 (ax+by-c) mod gcd=0

 ax+byc (mod gcd)

证毕

 当 ax+by=c 成立时，c=k*gcd

特殊的：

当 a，b 互质时，方程满足 ax+by=1

扩展欧几里得算法：

利用扩展欧几里得原理不仅可以实现求逆元，而且还可以得到 gcd(a,b)

递归边界：

当 b=0 时，a=gcd(a,b),x=1,y 取任意数 

代码实现：

int extend_gcd(int a,int b,int &x,int &y)
{
    int gcd=a;
    if(b!=0){
        gcd=extend_gcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
    else{
        x=1;
        y=0;
    }
    return gcd;
}

解决完扩展欧几里得算法之后，也就说我们可以解决逆元问题：当有一个一元线性同余方程 ax1(mod b) 时，也就是说我们可以将其看作方程 ax+by=1 的解，根据扩展欧几里得原理，很容易得出一组解 （x0,y0）

当要求解 ans=（a*b*c）%p 时，我们想将 b 去掉，了解取模运算的都知道，ans/b  =  (a*c)%p  这是不成立的

所以乘法逆元解决了这个问题，即 求解方程  bx1(mod p) ,这样方程两边  同时 *x 这样可以消去 b 的影响

最后

以上就是清脆导师为你收集整理的裴蜀定理 && 扩展欧几里得算法求逆元详解的全部内容，希望文章能够帮你解决裴蜀定理 && 扩展欧几里得算法求逆元详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。