乘法逆元的具体求法
发布日期:2021-07-14 01:03:49 浏览次数:47 分类:技术文章

本文共 1394 字,大约阅读时间需要 4 分钟。

费马小定理求逆元

  • 费马小定理:a是不能被质数p整除的正整数,则有 a^(p-1) ≡ 1 (mod p)
    求a关于p的乘法逆元,即为a*c≡ 1 (mod p),那么a^(p-2)就是a的逆元
  • Code
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    LL quickpow(LL x,LL n,LL Mod){
    LL ans=1; x%=Mod; while(n>0){
    if(n&1) ans=(ans*x)%Mod; //n%2==1 x=(x*x)%Mod; n/=2; } return ans; } LL getInv(LL a,LL mod){
    return quickpow(a,mod-2,mod); } //时间复杂度O(logMod),且当Mod为不能整除a的素数时可用,一般题目给出1e9+7; //当Mod-2过大的时候可以使用欧拉降幂防T,a^(Mod-2)%Mod=a^((Mod-2)%phi(Mod)+phi(Mod)) %Mod;

扩欧求逆元

  • 给定模数m,求a的逆相当于求解ax=1(mod m)
    这个方程可以转化为ax-my=1
    然后套用求二元一次方程的方法,用扩展欧几里得算法求得一组x0,y0和gcd
    检查gcd是否为1
    gcd不为1则说明逆元不存在
    若为1,则调整x0到0~m-1的范围中即可
  • Code
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
    LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法 {
    if(b==0){
    x=1,y=0; return a; } LL ret=exgcd(b,a%b,y,x); y-=a/b*x; return ret; } LL getInv(int a,int mod)//求a在mod下的逆元,不存在逆元返回-1 {
    LL x,y; LL d=exgcd(a,mod,x,y); return d==1?(x%mod+mod)%mod:-1; } //时间复杂度为O(logn),只要存在逆元均可求

线性推逆元

  • 求1,2,…,N关于mod的逆元(mod为质数)
  • Code
    1 2 3 4 5 6 7
    const int mod = 1000000009; const int maxn = 10005; int inv[maxn]; inv[1] = 1; for(int i = 2; i < 10000; i++)     inv[i] = inv[mod % i] * (mod - mod / i) % mod; //时间复杂度O(N),求1到N所有数的逆元

递归求逆元

  • Code
    1 2 3 4 5 6
    LL inv(LL i) {
    if(i==1)return 1; return (mod-mod/i)*inv(mod%i)%mod; } //O(logmod),mod是素数

转载地址:https://blog.csdn.net/cpongo3/article/details/89334336 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:不要62
下一篇:Intervals

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月25日 13时33分20秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

当集合a为空集时a的取值范围_1.1.2 集合间的基本关系 2019-04-21
vue 可合并表格组件_Vue实战046:详解Mixins混入使用和注意事项 2019-04-21
python包怎么做双重差分did分析_多变量相关性分析(一个因变量与多个自变量) 2019-04-21
fi sap 凭证冲销 稅_SAP中的成本要素 2019-04-21
mysql幻读是什么意思_MySQL中的幻读,你真的理解吗? 2019-04-21
mysql执行计划中性能最差的是_MySQL性能优化(七):MySQL执行计划,真的很重要,来一起学习吧... 2019-04-21
易语言执行mysql命令_易语言通过“打开”命令操作数据库 2019-04-21
mysql slave 1062_mysql主从同步slave错误1062 2019-04-21
mysql构造器_MySQL行构造器表达式优化(Row Constructor Expression) 2019-04-21
2008日志清理 server sql_SQL Server 2008 清除日志 2019-04-21
mac mysql root 权限_Mac平台重新设置MySQL的root密码 2019-04-21
mysql新增一列_MySQL-ProxySQL中间件 2019-04-21
mysql 30入门_30分钟带你快速入门MySQL教程 2019-04-21
kangle主机怎么配置MySQL_kangle web服务+easypanel主机控制面板快速搭建网站和数据库以及管理空间详细教程... 2019-04-21
mysql 翻页 存储过程_MySQl通用翻页(存储过程) 2019-04-21
2020word替换所有文本_Excel字符函数(5):REPLACE、SUBSTITUTE查找替换函数之区别... 2019-04-21
win10安装ipython_win10环境 ipython app.py 8080 这里为什么是ipython 这步无法启动 2019-04-21
假定在MYSQL_假定在名称为教学库的数据库中包含有学生、课程和选课三个表,它们的定义如下 - 问答库... 2019-04-21
mysql多字段存储过程_mysql 的存储过程_多字段 2019-04-21
python怎么创建字符串列表_如何在python列表中为每个字符串创建子列表? 2019-04-21