【x义x讲坛】浅谈模质数意义下的乘法逆元

[$$\color{green}\Large\texttt{『菜鸡的blog』}$$](https://www.luogu.org/blog/zyxxs/) 我们直接切入正题吧。 ## 问题一：什么是乘法逆元呢？ 简单来说就是这样：在$\pmod p$意义下，如果$a*a' \equiv 1$，那么我们就说$a'$是$a$的逆元。当然啦，反过来，$a$也是$a'$的逆元。 （如果$a,p$不互质的话$a$是没有逆元的） （在$p$不是素数的时候情况比较复杂，所以这一篇先介绍$p$为素数时的情况） ## 问题二：逆元有什么性质？ 逆元的性质可真是多了去了，比较重要的有一下几个： （在这些性质中，一般都有一个特例：0，所以我们就不谈$a=0$的情况了） ### 1.存在唯一性 对于$a$来说，它只会有一个，且一定有一个逆元。 这是为什么呢？ 我们先假设$a$有两个不相等逆元：$a'$和$a''$，那么一定有： $$a*a'\equiv a*a''\equiv1\pmod p$$ 不妨设$a'<a''$且$a''-a'=k$，那么 $$a*(a''-k)\equiv a*a'' \pmod p$$ $$a*a''-a*k\equiv a*a''\pmod p$$ $$a*k\equiv0\pmod p$$ 由于$a\neq 0$，所以$k\equiv 0\pmod p$，即$a'\equiv a''$，与假设矛盾，所以$a$只能有一个逆元。 至于逆元的存在性，读者自己思考一下吧。~~（就是你懒！）~~ ### 2.完全积性函数 为了接下来方便，我们把$a$的逆元表示为$inv[a]$吧。 这个性质是说： 两个数的逆元的积等于这两个数积的逆元，$inv[a]*inv[b]\equiv inv[a*b]$。 这点也不难证： 显然 $$a*inv[a]\equiv b*inv[b]\equiv 1 \pmod p$$ 那么 $$a*inv[a]*b*inv[b]\equiv1*1 \pmod p$$ 所以 $$(a*b)*(inv[a]*inv[b])\equiv1 \pmod p$$ 这不就是$(a*b)$的逆元的定义吗！ ### 3.$a*inv[b]\equiv a/b$ $\pmod p$ 显然 $$b*inv[b]\equiv 1 \pmod p$$ 两边都乘以$a$得 $$a*b*inv[b]\equiv a \pmod p$$ 也就是 $$a*inv[b]\equiv a/b \pmod p$$ **这个结论非常重要！** 有时候我们需要算出$a/b$ $mod$ $p$的值，用朴素的方法，我们只能在$a$上不断加$p$，直到它能被$b$整除为止。当$a,b,p$都很大的时候，这种方法就只能凉凉了，但如果有了逆元，我们就可以非常方便，快捷地求解。 ### 4.卖个关子 ~~不要打我~~ ## 问题三：逆元怎么求呢？ 嗯，逆元确实不错，但怎么求呢？ ### （单个）求法一：枚举法 枚举$k$，检查是否满足$a*k\equiv1$ $\pmod p$。 太蠢了…… ### （单个）求法二：费马小定理 费马小定理：当$p$为素数时，$a^{p-1}\equiv1$ $\pmod p$。 那么$a*a^{p-2}\equiv1$ $\pmod p$。 再看看，这是不是又是逆元的定义？快速幂求出$a^{p-2}$即可。 ### （单个）求法三：扩展欧几里得 寻找$a*x\equiv1$ （$mod$ $p$）的解$inv[a]$其实就相当于寻找方程$a*x+p*y=1$的解。 再一看：$a,p$一定互质，这不就是扩展欧几里得算法的标准形式吗！ ### （批量）求法四：欧拉筛 刚才讲的都是求单个$a$的逆元，但如果我们要求出$1$~$p-1$所有数的逆元呢？ 还记得逆元是完全积性函数吗？所以对于每个合数$a$，我们把所有它的因子的逆元筛出来再相乘即可。 所以我们可以直接把所有素数筛出来，对它们求逆元（二或三），再把它的逆元乘给它的倍数就可以了。 代码如下：（这里用的是快速幂，貌似扩欧比它更快） ``` #include <bits/stdc++.h> using namespace std; const int N=25000528; int p,n; int vis[N],pri[N]; int inv[N]; int mi(int i,int j) //分治快速幂 { if (!j) return 1; long long now=mi(i,j>>1); now=now*now%p; if (j&1) now=now*i%p; return (int)now; } int main() { cin>>n>>p; vis[1]=1,inv[1]=1; for (int i=2;i<=p-1;i++) { if (!vis[i]) pri[++pri[0]]=i,inv[i]=mi(i,p-2); for (int j=1;j<=pri[0];j++) { if (i*pri[j]>=p) break; inv[i*pri[j]]=inv[i]*inv[pri[j]]; if (i%pri[j]==0) break; } } for (int i=1;i<=n;i++) printf("%d\n",inv[i]); return 0; } ``` 不能过P3811……换成扩欧可能有救。 ### 求法五：线性递推 现在我们要求$k$的逆元。 令$a*k+b=p$。 $$b*inv[b]\equiv1 \pmod p$$ 把$b$换种表达，$p-a*k$： $$(p-ak)*inv[b]\equiv1 \pmod p$$ 那么 $$p*inv[b]-a*k*inv[b]\equiv1 \pmod p$$ 在$\pmod p$意义下$p\equiv0$，则 $$-a*k*inv[b]\equiv1 \pmod p$$ 观察$ak+b=p$，我们发现：$a=p/k,b=p\% k$（除号指整除），则最终 $$-(p/k)*inv[p \% k]*k\equiv1 \pmod p$$ 即 $$-(p/k)*inv[p\%k]\equiv inv[k] \pmod p$$ 神奇吧~ 这就得出了性质4，也是我们今天最后一个求法线性递推的原理了。 这个东西可以以线性递推的方式求$1$至$n$所有数的逆元，也可以以递归的方式求单个数的逆元。（不过似乎和exgcd一样也是辗转相除？） 实际使用的时候记得加上$p$来去掉负号。代码如下：（可过P3811） ``` #include<bits/stdc++.h> using namespace std; int N,p; int inv[25000528]; int main() { cin>>N>>p; inv[1]=1; for (int i=2;i<=N;i++) inv[i]=(long long)(p-p/i)*inv[p%i]%p; for (int i=1;i<=N;i++) printf("%d\n",inv[i]); return 0; } ``` ## 【谢谢观看】 ### 后记 感觉好多东西都没写到啊…… 还有，建议这一篇的各个式子再消化一下。毕竟，一下子来这么多数学公式确实很难接受。 ### 后记的后记（2019/8/6） 本次博客第一次大改。主要是标题字体字号修得更适合阅读，以及$\LaTeX$的问题，然后在开头放了一个本人博客的链接。 不知道你们有没有发现之前本博客的居中是拿\quad拼出来的……然后看看大概是中间位置就算居中了…… ~~怎么莫名感觉之前的自己比现在强呢~~