扩展欧几里得与乘法逆元

扩展欧几里得能求出形如a*x+b*y=gcd(a,b)的通解x,y。

我们设

a1*x1+b1*y1=gcd(a,b)   （1）

a2*x2+b2*y2=gcd(a,b)     (2)

并且a2=b1,b2=a1%b1=a1-(a1/b1*b1)

则（1）（2）相等可得a1*x2+b1*y1=b1*x2+[a1-(a1/b1*b1)]* y2

对应系数相等可得：x1=y2 ,y1=x2-a1/b1*y2;

如此迭代下去直到b=0时，有x=1,y=0; （此时gcd(a,b)即为a (n).)

递归往上赋值即可。

代码如下：

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    int d=a;  //d记录gcd
    if(b!=0)
    {
        d=exgcd(b,a%b,x,y);//下一步迭代
        int t=x;   //t记录x
        x=y;       //上一步的x等于下一步的y
        y=t-a/b*y; //上一步的y等于下一步的x(t)减去a/b*（下一步的y) （此时a，b是上一步的）
    }
    else
        x=1,y=0;  //迭代终点
    return d;
}

假设我们已经求出了a*x+b*y=gcd(a,b)的一组特解x0,y0；

设x，y为通解，x=x0+p,y=y0+q;

带入方程得a*(x0+p)+b*(y0+q)=c,化简得a*p+b*q=0 (因为a*x0+b*y0==c，消去了)

由于p，q为整数先设p=b,q=-a;

由于我们求出了gcd（a,b)  ,那么p=b/gcd(a,b) ,q=-a/gcd(a,b) //那么此时p，q一定为最简整数

由于我们找的是通解，则p=b/gcd(a,b)*t,q=-a/gcd(a,b)*t     //t为任意整数

那么通解：

x=x0+b/gcd(a,b)*t;

y=y0-a/gcd(a,b)*t;（t为任意整数）（很多博客上都没有解释这通解是怎么来的，还是自己写篇博客记录下吧）

我们现在要求a*x+b*y=c的通解只需将a*x+b*y=gcd(a,b)的通解都乘上c/gcd(a,b)即可。

我们先找到一组特解：x1=x0*c/gcd(a,b)  ,y1=y0*c/gcd(a,b);

则a*x+b*y=c的通解：

x=x1+b/gcd(a,b)*t;

y=y1-a/gcd(a,b)*t;  （t为任意整数）

那么我们求最小x时只需将对a*x+b*y=gcd(a,b）求出的特解x,y进行如下操作即可

x=x*c/gcd(a,b)

b=b/gcd(a,b)   

if(b<0)，b=-b;

x=x%b;      // 保证x最小

if(x<=0)//根据题目要求，大部分是最小正整数解，如果解可以为0得话，这里去掉0即可。

x+=b;   //此时t=1（即多加了1个b（这时的b已经除过了gcd（a,b)))

则此时的x即为最小值。若同时需要求y的话，直接根据此时得x求出即可。

由 a*x+b*y=c

得y=(c-a*x)/b;

代码如下：

void cal(LL a,LL b,LL c)
{
    LL x,y;
    LL gcd=exgcd(a,b,x,y);
    if(c%gcd)  //如果gcd不是c的因子的话，就不可能相遇
        cout<<"Impossible"<<endl;
    else
    {
        x*=c/gcd; //化为a*x+b*y=c模型
        b/=gcd;
        if(b<0)
            b=-b;
        LL ans=x%b;
        if(ans<=0)
            ans+=b;
        cout<<ans<<endl;
    }
}

二：乘法逆元：

解法1：扩展欧几里得：由a*x=1(mod p).  由同余性质得 a*x+k*p=1,这即为扩欧形式，直接扩欧求就好了。

解法2：费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

那么a*(a^(p-2))=1（mod p).即a^(p-2)为a在mod p下的逆元。而a^(p-2)可以用快速幂求得。这种方法限制较多，使用时要密切注意。

解法3：线性递推：我们用inv[i]代表i在mod p下的逆元,(注意线性递推只能求1～p之间的逆元！）

易知：inv[1]=1，设p=k*i+r . 此时k=p/i(整数下的除法）,r=p%i。

上式可化为k*i+r=0(mod p);

上式两边同时乘以inv[i],inv[r]得：k*inv[r]+inv[i]=0(mod p);

则inv[i]=-k*inv[r]=-(p/i)*inv[p%i]%p;

为了保证其为非负得：

得：inv[i]=(p-p/i)*inv[p%i]%p;

解法4：阶乘递推：我们用c[i]代表 i 的阶乘。用f[i]代表i ！的逆元。

由 f[i]=1/(i !) (mod p)  . f[i+1]=1/（i+1！）（mod p).

得f[i]=f[i+1]*(i+1) (mod p).

由 inv[i]=1/i(mod p).

得 inv[i]=1/(i !)*(i-1)!(mod p).

最后

以上就是阔达跳跳糖为你收集整理的扩展欧几里得与乘法逆元的全部内容，希望文章能够帮你解决扩展欧几里得与乘法逆元所遇到的程序开发问题。

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