1. 首页
  2. 模板

乘法逆元模板

乘法逆元的定义
对a∈Zm,存在b∈Zm,使得a×b ≡1 (mod m),则称b为a的乘法逆元

条件

对于乘法逆元:在mod m的操作下(即Zm中),a存在乘法逆元当且仅当a与m互质不定方程ab+mx=1的任意一组整数解(b,x),b就是a的乘法逆元。具体计算可以使用扩展欧几里德算法(Extended-GCD)。

费马小定理求逆元

利用欧拉函数

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/951 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40