逆元 笔记

问题引入

对于任意两个数字a，b和一个模数mod，我们不难得出以下三个式子（均取模mod）：

• (a+b)%mod=a%mod+b%mod;
• (a-b)%mod=a%mod-b%mod;
• (a*b)%mod=a%mod*b%mod.

然后，您就会发现唯独缺了一个：

• (a/b)%mod=a%mod/b%mod.

显然这是不成立的。下面举出两组反例：

1. 当a=4，b=7，mod=5，(a/b)%mod=(4/7)%5=4/7，a%mod/b%mod=4%5/7%5=4/2=2，显然4/7≠2；
2. 当a=11，b=6，mod=6，(a/b)%mod=(11/6)%6=11/6，a%mod/b%mod=11%6/6%6=5/0=RE！

所以，为了解决这个棘手的问题，我们不得不引入一个新的概念——逆元。

何为逆元

定义

• 我们定义模mod意义下关于除数（分母）b的逆元i使得(a/b)%mod=(a*i)/mod=a%mod/i%mod。

费马小定理

• 设i为模mod意义下b的逆元，则i=amod-2（a，mod互质）。

线性递推求逆元（划重点）

在OI竞赛中，OIer常被要求将答案取模。然而对于如上所述的除法运算，取模并不是那么简单；同时，若有多组数据，针对每组数据一个个求逆元也不是一件简单的事。由此，我们需要推导线性递推求逆元的公式。

公式推导&证明

1. 我们对mod进行有余数除法，即mod÷i=⌊mod÷i⌋……mod%i，变形得mod=⌊mod÷i⌋×i+mod%i。
2. 由于是在模mod意义下，所以我们将等式左侧的mod取模为0，即0=⌊mod÷i⌋×i+mod%i。
3. 整理式子，得-mod%i=⌊mod÷i⌋×i，再将等式两边同时除以[(mod%i)×i]，得：
4. -i-1=⌊mod÷i⌋÷(mod%i)，即i-1=-⌊mod÷i⌋÷(mod%i)，即i-1=-⌊mod÷i⌋×(mod%i)-1。

代码实现

我们设inv[n]为n的逆元，其中需要注意的是，inv[1]=1，又根据上方推导的结果，inv[i]=(mod-mod/i)*inv[mod%i]%mod（C++，除法下取整）。

inv[1]=1;
for(int i=2;i
    <maxn;i++) inv[i]="(mod-mod/i)*inv[mod%i]%mod;</code"></maxn;i++)>

<p> </p> <p> </p> <p>短 小 精 悍</p> <p> </p>