乘法逆元相关知识

在a和b很大的情况下,如果我们要算(a+b)%p,则其等于(a%p+b%p)%p;乘法也一样:(ab)%p=((a%p)(b%p))%p。那么如果我们要算(a/b)%p呢?它依然等于((a%p)/(b%p))%p吗?

很显然不等于。反例就不举了(太多了~)。

这时候我们就需要用到乘法逆元(Multiplicative inverse modulo)。乘法逆元的定义:满足ak≡1 (mod p)的k值就是a关于p的乘法逆元(本文中mod等同于%)(前面那个ak≡1 (mod p)的意思是a*k mod p≡1 mod p,称为同膜……这个写法我咨询了XCW大佬才看懂……)。

我们可以通过先求b关于p的乘法逆元k,再将a乘上k再模p,即(ak)%p,得出我们要的(a/b)%p。(ak)%p=(a/b)%p。(前提是a、p互质)证明如下:

根据b*k≡1(mod p),有b*k=p*x+1。
则k=(p*x+1)/b。
将k=(p*x+1)/b代入(a*k)%p,得:
原式=(a*(p*x+1)/b)%p
    =(a*p*x/b+a/b)%p;
根据(a+b)%p=(a%p+b%p)%p,有
原式=(p*(a*x/b)%p+a/b)%p
    =(a/b)%p
即(a*k)%p=(a/b)%p.

为什么a和p要互质呢?因为原来的a*k≡1 (mod p)可以化成ax+by=1的形式,那么要使其有解,a、b的最大公因数必须是1,即gcd(a,b)=1。

求逆元

逆元一般可以用拓展欧几里得算法求。以下是代码:

void Exgcd(int a,int b,int &x,int &y){
     if (b==0) x=1,y=0; else Exgcd(b,a%b,y,x),y-=a/b*x;
}
int get(int a,int b,int p){//这个函数的作用是求(a/b)%p
    int x,y;
    Exgcd(b,p,x,y);
    return (x+p)%p;//考虑负数情况
}

参考:
(XCW大佬的博客)http://blog.csdn.net/qq_41357771/article/details/78823967

发表评论

电子邮件地址不会被公开。 必填项已用*标注