逆元

刺骨的言语ヽ痛彻心扉 2021-09-07 06:10 355阅读 0赞

参考于此篇博客：[https://www.cnblogs.com/kongbursi-2292702937/p/10582258.html][https_www.cnblogs.com_kongbursi-2292702937_p_10582258.html]

逆元定义：

对于a\*b≡1(mod m)，b是a在模m下a的逆元。

首先对于同余符号≡，如 a≡b%m 表示的意思是a%m=b%m,a、b模m后余数相同。

逆元可以看作一个数的倒数 c \* b≡1(mod m)(b为c的逆元)  
可得(a/c)%m=(a\*b)%m  
推导过程：(a/c)%m=(a/c)\*1%m=(a/c) \* c \* b%m=(a \* b)%m

由费马小定理：a、m是互质的正整数，有a^(m-1)≡1(mod m)  
可得：a的逆元为：a^(m-2)  
推导过程：a^(m-1)≡1(mod m)=a\*a^(m-2)≡1(mod m)，由逆元定义可得 a逆元=a^(m-2)  
其实就是转变为通过快速幂找到逆元。

快速幂板子（Mod还要自己定义个全局变量）

ll qpow(ll a, ll b) { 
    	ll ans = 1, base = a;
    	while (b) { 
    		if (b & 1) ans = ans * base % Mod;
    		base = base * base % Mod;
    		b >>= 1;
    	}
    	return ans;
    }

逆元常运用于组合数：[https://blog.csdn.net/asbbv/article/details/111321575][https_blog.csdn.net_asbbv_article_details_111321575]

[https_www.cnblogs.com_kongbursi-2292702937_p_10582258.html]: https://www.cnblogs.com/kongbursi-2292702937/p/10582258.html
[https_blog.csdn.net_asbbv_article_details_111321575]: https://blog.csdn.net/asbbv/article/details/111321575

发表评论取消回复

表情：

评论列表（有 0 条评论，355人围观）

还没有评论，来说两句吧...

相关阅读

相关乘法逆元整理

乘法逆元 1.费马小定理 > 如果 $ a,p $ 互质，那么 $ a^\{p-1\} ≡ 1(mod p) $ > 又由逆元方程知 $ a\*x ≡ ...

约定不等于承诺〃/ 2024年04月20日 10:25/ 0 赞/ 31 阅读

相关线性求逆元

线性求逆元求1~n在%mod意义下的逆元 ![1735240-20190814082511164-1340216219.png][] mi[1]=1;

以你之姓@/ 2023年08月17日 15:35/ 0 赞/ 72 阅读

相关逆元求组合数

逆元简介同余符号 ≡ 先bb一下 ≡，这个符号有三个意思，再这里用到的意思为“同余符号”。[≡ 的介绍][Link 1] 两个整数a，b，若它们除以整数m所得的

ゝ一纸荒年。/ 2023年07月17日 12:42/ 0 赞/ 33 阅读

相关数论-同余与逆元

文章目录同余一元线性同余方程逆元逆元与除法取模例题 HDU-5976 同余 -----------

曾经终败给现在/ 2022年11月25日 14:30/ 0 赞/ 139 阅读

相关逆元详解求逆元的方法汇总

[基础知识][Link 1] [求乘法逆元的几种方法][Link 2] [逆元详解][Link 3] [Link 1]: http://blog.csdn.net/fe

秒速五厘米/ 2022年06月13日 05:45/ 0 赞/ 184 阅读

相关详解--乘法逆元

今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。对于正整数![20140613102654328][]和![20140613

怼烎@/ 2022年06月11日 07:48/ 0 赞/ 311 阅读

相关乘法逆元 51Nod - 1256——同余定理+逆元(乘法逆元) (拓展欧几里得算法求逆元)

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K \ M % N = 1，如果有多个满足条件的，输出最小的。 Input 输入2个数

比眉伴天荒/ 2022年05月19日 13:41/ 0 赞/ 217 阅读

相关 A/B——同余定理+逆元（除法逆元）

同余定理: 数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(modm)

太过爱你忘了你带给我的痛/ 2022年05月19日 11:18/ 0 赞/ 245 阅读

相关求逆元基本方法

乘法逆元小结 > 乘法逆元，一般用于求 > > $\\frac\{a\}\{b\} \\pmod p$ > > 的值（$p$ 通常为质数），是解决模意义下分数数值的必要手

旧城等待，/ 2021年11月22日 08:10/ 0 赞/ 406 阅读

相关逆元

参考于此篇博客：[https://www.cnblogs.com/kongbursi-2292702937/p/10582258.html][https_www.cnblogs

刺骨的言语ヽ痛彻心扉/ 2021年09月07日 06:10/ 0 赞/ 356 阅读