概述
给定一a，逆元是指使a*x=1 (mod p)成立的x
一、扩展欧几里得
O ( logn )
在前面的博客中已经提过了
http://blog.csdn.net/jerry99s/article/details/78169178
a*x=1 (mod p)
a*x=p*(-y)+1
a*x+p*y=1;
扩展欧几里得求x
二、快速幂
O ( logn )
费马小定理说：若p是质数且gcd(a,p)=1，那么 a^(p-1)≡1 (mod p)
所以，逆元x=a^(-1)=a^(p-2) (mod p)
注意：这里要求模数p必须为质数
三：递推求1~n每个数逆元
O ( n )
公式：inv[i] = (p-p/i) * inv[p%i] % p;
void get_inverse(int n, int p) {
inv[1] = 1;
for (int i = 2; i <= n; i++) {
inv[i] = (p - p / i) * inv[p % i] % p;
}
}最后
以上就是野性小鸭子为你收集整理的求逆元的几种方法的全部内容，希望文章能够帮你解决求逆元的几种方法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复