扩欧与乘法逆元

扩展欧几里得能求出形如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).

 

上一篇:「JLOI2015」骗我呢 解题报告?


下一篇:AtCoder Grand Contest 019 F-yes or no