• 前言
• 有关乘法逆元定义
• 费马小定理
• 乘法逆元(编程计算)
  • 有关乘法逆元题目
    • (AtCoder - 1974)いろはちゃんとマス目 / Iroha and a Grid(乘法逆元+组合计数)

前言

看到这里的小盆友们千万不要觉得这个东西很难,其实就是个1+1->1(1个定义+1个定理->1坨乘法逆元).Let’s begin.

有关乘法逆元定义

这个我们就不要玩笑了,来，直接看定义：
乘法:是指将相同的数加起来的快捷方式。(呵呵呵)
逆元素：指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。(???)
乘法逆元:群G中任意一个元素a，都在G中有唯一的逆元a‘,具有性质aa’=a’a=e，其中e为群的单位元。(!!!) 咳咳,是不是觉得最后两个很高深？其实第二个不用管,你只需要知道第3个，你可以这样理解:
有一个数a,一个模数M，当gcd(a,M)=1(就是a,M互质)" role="presentation">gcd(a,M)=1(就是a,M互质)$$gcd(a,M)=1(就是a,M互质)$$满足时有ab≡1(modM)" role="presentation">ab≡1(modM)$$ab\equiv 1(modM)$$此时b称为a的乘法逆元,同时此时a也为b的乘法逆元.又可以说此时a,b互为乘法逆元.
那么此时我们就可以表示出：
a≡b−1≡1b(modM)" role="presentation">a≡b−1≡1b(modM)$$a\equiv b^{-1}\equiv \frac{1}{b}(modM)$$
可以简单、宽泛地甚至有点错误地理解为分数可以参加同余运算？
是不是思路清晰了很多(然并卵…)好吧,我们来举个例子：
当a=4,M=7时，此时4,7互质,那我们凑一凑就可以凑出: 4*2≡1(mod 7)，呀！一组乘法逆元就出现了！此时4,2就互为乘法逆元.(hhh…)再来俩例子: 当a=5,M=8时，此时5,8互质,那我们凑一凑又可以凑出: 5*5≡1(mod 8)，呀！一组乘法逆元又出现了！此时5,5就互为乘法逆元. 当a=10,M=3时，此时10,3互质,那我们凑一凑又可以凑出: 10*1≡1(mod 3)，呀！一组乘法逆元又出现了！此时10,1就互为乘法逆元. 我们可以发现,在同一M下当gcd(a,M)=1时可能有许多b满足ab≡1(mod M)比如第一个例子 4*2≡1(mod 7),同时4*9≡1(mod 7),4*16≡1(mod 7),说明同一a可能与多个b互为乘法逆元.
好吧,现在对乘法逆元大概了解一丢丢了吧？
补充一下,这里的b我们又可以记作inv(a)

费马小定理

至于怎么证明的,呵呵,作者并不知道,貌似是跟剩余系有关,有兴趣的盆友们自己查查吧，它的内容是：
假如p是质数，且gcd(a,p)=1" role="presentation">gcd(a,p)=1$$gcd(a,p)=1$$那么 ap≡a(modp)" role="presentation">ap≡a(modp)$$a^p\equiv a(modp)$$ ap−1≡1(modp)" role="presentation">ap−1≡1(modp)$$a^{p-1}\equiv 1(modp)$$
好吧,我们来试一试：
当a=8，p=3时gcd(8,3)=1，所以8^2≡1(mod 3)
当a=5，p=2时gcd(5,2)=1，所以5^1≡1(mod 2)
当a=4，p=5时gcd(4,9)=1，所以4^4≡1(mod 5)
…我们就默认它是对的吧…

乘法逆元(编程计算)

那么,今天最重要的来了
当有a,M满足gcd(a,M)=1,我们根据费马小定理可以得到：
aM−1≡1(modM)" role="presentation">aM−1≡1(modM)$$a^{M-1}\equiv 1(modM)$$
那么变一下形：
a∗aM−2≡1(modM)" role="presentation">a∗aM−2≡1(modM)$$a\ast a^{M-2}\equiv 1(modM)$$
这个东西是不是满足上面的乘法逆元定义？
所以,此时a与a^(M-2)互为乘法逆元
那么
aM−2≡a−1≡1a(modM)" role="presentation">aM−2≡a−1≡1a(modM)$$a^{M-2}\equiv a^{-1}\equiv \frac{1}{a}(modM)$$
我们有知道模运算有乘法结合律
ba≡b∗a−1≡b∗aM−2(modM)" role="presentation">ba≡b∗a−1≡b∗aM−2(modM)$$\frac{b}{a}\equiv b\ast a^{-1}\equiv b\ast a^{M-2}(modM)$$
这说明,如果当分数形如b/a(a!=0且为整数)参加模运算时,且gcd(a,M)=1，那么b/a就同余b*a^(M-2)
一个分数转化成了整数,神不神奇？？
所以,在gcd(a,M)=1时，除以a等价于乘a的乘法逆元

有关乘法逆元题目

(AtCoder - 1974)いろはちゃんとマス目 / Iroha and a Grid(乘法逆元+组合计数)

这是我的另一篇博客….题目大意和跟乘法逆元没有关系的部分(是关于计数方面问题)先在里面看了吧(好吧,我这个可爱的人在刷阅读量)
…………………………………..
好了,相信你已经看到了这道题组合计数长这个样子：
(∑i=b+1WC(H−a+i−2,i−1)∗C(W+a−i−1,a−1))%MOD" role="presentation">(∑i=b+1WC(H−a+i−2,i−1)∗C(W+a−i−1,a−1))%MOD$$(\sum _{i=b+1}^{W}C(H-a+i-2,i-1)\ast C(W+a-i-1,a-1))\mathrm{\%}MOD$$
什么,你看不懂？那这种你看得懂了吧？ for(int i=b+1;i<=w;i++)//推导计数方法 ans=(ans+C(h-a+i-2,i-1)*C(a+w-i-1,a-1)%MOD)%MOD; 好了,最重要的问题来了,C(m,n)怎么算？？
我们知道,当m,n很小时,我们可以直接硬算.But,这里H,W都是100000级别的数,这样做肯定会TLE的,于是我们就要预处理：
我们知道C(m,n)是这样算的：
C(m,n)=m!n!(m−n)!" role="presentation">C(m,n)=m!n!(m−n)!$$C(m,n)=\frac{m!}{n!(m-n)!}$$
看到没有?阶乘！于是我们可以把阶乘s[i]都给,把组合上半部分预处理出来： for(int i=1;i<=2*MAXN;i++) s[i]=s[i-1]*i%MOD; 这里为什么是2*MAXN?你看看我们的计数式子就知道了
问题是组合下半部分怎么搞？？我们知道,模运算中遇到除法是不能直接除的,因为有模数MOD但我们是不是可以变形成这样？
C(m,n)=(m!1n!(m−n)!)%MOD" role="presentation">C(m,n)=(m!1n!(m−n)!)%M