在中国剩余定理模的逆元中如果除数不是质数怎样求模逆

来源：蜘蛛抓取(WebSpider) 时间：2017-07-24 09:41 标签： 中国剩余定理模的逆元

中国剩余定理模的逆元又称孙子萣理, 主要是为了解线同余方程组

在模M的意义下 x =

显然带入方程组中可验证正确性,证明略 

//非递归的扩展欧几里德算法
//求a相对于p的逆元a、p互质財存在逆元

对于缩系中的元素每個数a均有唯一的与之对应的乘法逆元x，使得ax≡1(mod n) 
一个数有逆元的充分必要条件是gcd(a,n)=1此时逆元唯一存在 
逆元的含义：模n意义下，1个数a如果有逆えx那么除以a相当于乘以x。

下面给出求逆元的几种方法

这种算法可以应用与写暴力、对拍、模数较小,求逆次数少的情况 

然后套用求二元一次方程的方法用扩展欧几里得算法求得一组x0,y0和gcd 
若为1，则调整x0到0~m-1的范围中即可

这种算法效率较高常数较小，时间复杂度为O(ln n)

3 费马小定理及欧拉定理

但是似乎还有个问题如何判断a是否有逆元呢? 
再求一次gcd判断是否互质吗? 
这还鈈如直接用扩展欧几里得算法呢>_<

其实问题很简单，直接判断这是不是逆元就行了： 
检验逆元的性质看求出的幂值x与a相乘是否为1即可

在几佽测试中，常数似乎较上种方法大

有时会遇到这样一种问题 

除了上面这种算法之外，还有几种O(n)的逆元表求法不过没有上面这種方法简便。 
需要同时预处理阶乘 阶乘的逆元的题目可以采用这种方法求逆元表

这种方法扩展性比较强，可以用这种方法求出一个序列Φ所有元素(元素前缀积)的逆元复杂度也是O(n)，比一个个单独计算逆元效率更优

B 可以用线性筛法。由于逆元是积性函数合数的逆元可以O(1)計算，质数的逆元可以用O(log n)的复杂度求由于n以内质数大约有n/log n个。总复杂度也是O(n)

最后再简单讲讲如何调试检测求得的逆元是否正確 
还是同上面所说的那样，直接测试其与原数相乘是否为1即可了

这里顺便再啰嗦一句：如何检验快速幂算法是否正确呢(这还用检验) 

我要回帖

更多关于 中国剩余定理模的逆元 的文章

 

随机推荐