设为首页 加入收藏

TOP

乘法逆元及其三种求法
2023-09-09 10:25:46 】 浏览:91
Tags:元及其

什么是逆元?

如果 \(ax\equiv 1(\mod p)\),且 \(a\)\(p\) 互质 \(\gcd(a,p)=1\),则 \(x\)\(a\) 在模 \(p\) 意义上的逆元,也就是 \(a\equiv x^{-1} (\mod p)\)

\(\mathcal{first}\).费马小定理求逆元

我们知道费马小定理是:\(a^{p-1}\equiv 1(\mod p)\)
两边同时乘上 \(a^{-1}\),就转换成 \(a^{p-2}\equiv a^{-1}(\mod p)\)。用一个快速幂即可得到 \(a\) 的逆元。

int pow(int a, int b, int p){
    int ret=1;
    while(b){
        if(b&1)
            ret=(ret*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ret;
}
int inv(int a, int p){
    return pow(a,p-2,p);
}

\(\mathcal{second}\).拓展欧几里得求逆元

我们知道,拓展欧几里得是用来求解 \(ax+py=\gcd(a,p)\),又因为 \(p\) 是质数,即 \(ax\equiv 1(\mod p)\)。所以方程的 \(x\) 就是 \(a\)的逆元。


void exgcd(int a,int b){
  	if(!b){x=1,y=0;return ;}
  	exgcd(b,a%b);
  	int t=x;
 	 x=y,y=t-a/b*y;
}
int main(){
  	int n,p;
  	scanf("%d%d",&n,&p);
  	exgcd(i,p);
  	cout<<(x%p+p)%x;
  	return 0;
}

third.线性推逆元

首先我们设,\(k=\lfloor{\frac{p}{i}}\rfloor,r=p\mod i\),那么就能知道 \(k\times i+r\equiv 0(\mod p)\)

然后我们将等式两边同时乘上 $i^{-1} r^{-1} $,就能得到 \(k\times r^{-1}+i^{-1}\equiv 0(\mod p)\)

\(k\times r^{-1}\) 移到右边去,即 \(i^{-1} \equiv -k\times r^{-1}(\mod p)\)

也就是 \(i^{-1}\equiv -\lfloor{\frac{p}{i}}\rfloor\times(p\mod i)^{-1} (\mod i)\)

inv[1]=1;
for(int i=2;i<p;++i)
    inv[i]=(p-p/i)*inv[p%i]%p;
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇《CUDA编程:基础与实践》读书笔.. 下一篇C++算法之旅、05 基础篇 | 第二章..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目