逆元

若有$a\times b \equiv 1(\text{mod } m)$，则称$b$是$a$在模$m$意义下的逆元……

一 引入

1 定义

若有$a\times b \equiv 1(\text{mod } m)$，则称$b$是$a$在模$m$意义下的逆元（inv）。逆元只在取模意义下是有意义的，因此逆元应该小于模数（虽然大于模数对上面的同余方程成立并没有影响）。

2 应用

若要求$(a\div b) \text{ mod } m$，直接计算会遇到精度问题。

设$c$是$b$的逆元，因为存在$cb\equiv 1(\text{mod }m)$，故$\dfrac{a}{b} \equiv \dfrac{a}{b}\times 1 \equiv \dfrac{a·b·c}{b}( \text{mod } m)$。
故可知$a\div b\equiv ac( \text{mod } m)$。

这样计算就避免了精度问题。

---

二 逆元的求法

1 费马小定理

• 费马小定理：对于整数$a$和质数$p$，若$a,p$互质，则总存在$a^{p-1} \equiv 1(\text{mod }p)$

于是不难发现：若要求$a$在模$p$意义下的逆元，且$p$是质数时，一定有 $a^{p-1} \equiv a\times a^{p-2} \equiv 1 (\text{mod m})$。
故当$p$是质数且$a,p$互质时，$a$在模$p$意义下的逆元为$a^{p-2}$。

用快速幂取模运算$a^{p-2}$就好了。

代码：

#define LL long long

LL QuickPow(LL a,LL b,int m){ //快速幂取模 (a^b)%m
    LL base = a%m,rec = 1;
    while(b){
        if(b & 1) (rec *= base) %= m;
        (base *= base) %= m;
        b >>= 1;
    }
    return rec;
}
LL QueryInv(LL x,int m){ //求x在mod m意义下的逆元 
    return QuickPow(x,m-2,m);
}

2 扩展欧几里得

当$a,m$不互质时呢。此时需要解一个单变元模线性方程$ab\equiv 1(\text{mod } m)$，具体解法在后面的博文里面会提到，这里只给出代码：

LL a,m;

LL gcd(LL a,LL b){
    return b ? gcd(b,a%b):a;
}

//用ExGcd求不定方程 ax+by = c的一组特解(x0,y0)
//通解: x=x0+i*kx,y=y0-i*ky (i = 0,±1, ±2, ...)
void _exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x = 1; y = 0;
        return;
    }
    _exgcd(b,a%b,x,y);
    int t = x; x = y; y = t-(a/b)*y;
}
bool ExGcd(LL a,LL b,LL c,LL &x,LL &y,LL &kx,LL &ky){
    LL g = gcd(a,b);
    if(c % g) return false; //无解
    
    _exgcd(a,b,x,y);
    LL kc = c/g;
    x *= kc; y *= kc;
    kx = b/g; ky = a/g;
    return true;
} 
//求模线性方程 ax ≡ b(mod m)的最小非负整数解x0
//化成ax-my = b 
//通解x = x0+i*k 
bool LineModEqu(LL a,LL b,LL m,LL &x,LL& k){
    LL y,kx,ky;
    if(!ExGcd(a,m,b,x,y,kx,ky)) return false;
    k = kx; 
    x %= k;
    x = (x+k)%k; //取非负整数
    return true;
}

//求a的逆元b ab ≡ 1(mod m)
LL inv(LL a,LL m){
    LL b,k;
    if(!LineModEqu(a,1,m,b,k)) return -1;
    return b;
}

3 线性递推求逆元

若要求$[1,n]$内所有的数在模$m$意义下的逆元，显然可以求$n$次快速幂取模，复杂度$O(nlog_2 n)$。
那么有没有办法可以在$O(n)$的时间内求出所有的逆元呢？

首先一定有$\text{inv}[1]=1$恒成立，那么就可以用到下面这个递推式：
$$\text{inv}[i] = (m-\lfloor\dfrac{m}{i}\rfloor)\times \text{inv}[m\text{ mod }i]\text{ }\text{ }(\text{mod }m)$$

推导：
设$a = \lfloor\dfrac{m}{i}\rfloor,b= m\text{ mod }i$，则有$m = a\times i +b$
由$m = a\times i +b \Rightarrow ai+b \equiv 0(\text{mod }m)\Rightarrow b\equiv -ai(\text{mod }m)$
同余号两边同除以$i\times b$，得$-a\div b \equiv 1\div i (\text{mod }m)$

引入$b$的逆元$\text{inv}[b]$和$i$的逆元$\text{inv}[i]$，得 $-a\times\text{inv}[b] \equiv \text{inv}[i]$ $(\text{mod }m)$
代入$a = \lfloor\dfrac{m}{i}\rfloor,b= m\text{ mod }i$，得 $-\lfloor\dfrac{m}{i}\rfloor·\text{inv}[m\text{ mod }i] \equiv \text{inv}[i]$ $(\text{mod }m)$

又因$m\equiv 0(\text{mod }m)$，故$m-\lfloor\dfrac{m}{i}\rfloor\equiv -\lfloor\dfrac{m}{i}\rfloor (\text{mod }m)$。
所以有$\text{inv}[i] = (m-\lfloor\dfrac{m}{i}\rfloor)\times \text{inv}[m\text{ mod }i] \text{ }\text{ }(\text{mod }m)$。

为什么不用$-\lfloor\dfrac{m}{i}\rfloor$ ，而用$(m-\lfloor\dfrac{m}{i}\rfloor)$ 呢？
因为$-\lfloor\dfrac{m}{i}\rfloor < 0$，那么求出来的逆元也可能是个负数，而我们规定逆元总为正数。

代码：

int n,p;
int inv[CN];

n = read(); p = read();
    
inv[1] = 1; 
for(int i=2;i<=n;i++)
    inv[i] = (LL)(p-p/i)*inv[p%i]%p;