乘法逆元总结

本文移植自个人的原博客（原文）

乘法逆元的定义

若$ax≡1(modp)$, 则称$a$关于模$p$的乘法逆元为$x$。

当$a$与$p$互质时，$a$关于模$p$的乘法逆元有解。如果不互质，则无解。如果$p$为质数，则从$1$到$p-1$的任意数都与p互质，即在$1$到$p-1$之间都恰好有一个关于模$p$的乘法逆元。且$1$到$p-1$中的所有数的逆元对应$1$到$p-1$中的所有数，既是单射也是满射。

逆元的求解

扩展欧几里得算法

逆元一般通过$ExGCD$求解，该方法的时间复杂度为$O(logn)$。

int x, y;//NOIP 同余方程    
int extgcd(int a, int b, int &x, int &y)    
{    
    if (b == 0)
    {    
        x = 1;    
        y = 0;    
        return a;    
    }    
    int gcd = exgcd(b, a % b, x, y);    
    int tmp = x;    
    x = y;    
    y = tmp - (a/b) * y;    
    return gcd;    
}    //inv[n]=(x%p+x)%p;

费马小定理

当$p$为质数时，同样可以通过费马小定理求解。

已知$n^{p−1}≡1(modp)$(费马小定理)

那么$inv[n]=n^{p−2}(modp)$。该方法的时间复杂度为$O(logn)$（快速幂）。

线性求前n项的逆元

$$inv[n]=(p-p/n) * inv[p \ mod \ n]$$

递推求前n项的阶乘逆元

该方法较简单易懂，理论复杂度是上一个方法的$3$倍。据说在某些奇怪的时刻会跑的比上面快。（因为数组的连续访问）

//fac为阶乘，rev为阶乘的逆元。
fac[0]=fac[1]=1;
for(int i=2;i<=N;i++)fac[i]=fac[i-1]*i%mod;
rev[N]=mod_pow(fac[N],mod-2);//mod_pow为带取模的快速幂
for(int i=N-1;i>=0;i--)rev[i]=rev[i+1]*(i+1)%mod;
//可以通过阶乘逆元再一次循环求逆元

相关习题

T1

已知$\sum_{i=1}^{p-1} \frac 1 i = \frac A B $,其中$p$为奇质数，求证$A≡0(modp)$

证明

设$T=lcm(1,2,…,p−1)$

则有

$\sum_{i=1}^{p-1} \frac 1 i = 11/i=(T/1+T/2+…+T/(p−1))/T$

此时只需证明

$T/1+T/2+…+T/(p−1)≡0(modp)$

根据性质（见上）我们可以知道，$1$到$p-1$中所有数的逆元对应$1$到$p-1$中的所有数，则原式可以化简为

$1+2+…+(p−1)≡0(modp)$

$p∗(p−1)≡0(modp)$

得证。

T2 SDOI2008 沙拉公主的困惑

题目描述

大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为$1$到$N$的阶乘，但是，政府只发行编号与$M!$互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对$R$取模后的答案即可。$R$是一个质数。

输入第一行为两个整数$T,R$。$R<=10^9+10,T<=10000$，表示该组中测试数据数目，$R$为模数。

后面$T$行，每行一对整数$N,M$，见题目描述。

输出共$T$行，对于每一对$N,M$，输出$1$至$N!$中与$M!$素质的数的数量对$R$取模后的值。

对于$100 \ percent$的数据，$1 < = M < = N < = 10000000$

题解

题意明确$m<=n$，且易知$m!|n!$那么只需要算出$\varphi(m!)$即可，根据欧几里得算法可知最后的答案即为$\varphi(m!)∗n!/m!(modp)$

对于$\varphi(m!)$来说，$m!$的值过大，只能利用通项公式来求解，易知$m!$的所有质因数即为$1$到$m$中所有的质数，由于通项公式中涉及模运算下的除法，所以应先处理一下逆元。

#include<cstdio>
#include<iostream>
const int M = 1e6+1;
using namespace std;
bool vis[M+100];
long long prime[500500],ans[M+100],fac[M+100],rev[M+100];
int n,m,p,T,tot;
int main()
{
    scanf("%d%d",&T,&p);

    for(int i=2;i<=M;i++)
    {
        if(!vis[i])prime[++tot]=i;
        for(int j=1;j<=tot&&prime[j]*i<=M;j++)
        {
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }
    fac[1]=1;
    for(int i=2;i<=M;i++)fac[i]=fac[i-1]*i%p;
    rev[1]=1;
    for(int i=2;i<=M&&i<p;i++)rev[i]=(p-p/i)*rev[p%i]%p;
    ans[1]=1;
    for(int i=2;i<=M;i++)
    {
        if(!vis[i])    ans[i]=ans[i-1]*(i-1)%p*rev[i%p]%p;
        else                ans[i]=ans[i-1];
    }
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",fac[n]*ans[m]%p);
    }
}