乘法逆元

数！论！

逆元是个好东西，不会也要背板子。

定义
若 $ax\equiv 1 \pmod p$ ，则称 $x$ 为 $a$ 在模 $p$ 意义下的乘法逆元，记作 $a^{-1}$ 。

此时存在 $x/a\equiv xa^{-1} \pmod p$ 。这样就可以方便的计算在模意义下的除法操作。

例：在 $p=13$ 时， $3\times 9 \equiv 1 \pmod {13}$ 。则对于任意 $x$ ，都有 $x\div 3\equiv 9x \pmod {13}$ 。
验证一下： $27\div 3 = 9, 27*9 = 243 = 18 \times 13 + 9$ 。

为什么？
为什么若 $aa^{-1}\equiv 1 \pmod p$ ，则 $x/a\equiv xa^{-1} \pmod p$ 呢？

我们来证明一下：
$x/a\equiv x/a \pmod p$
同余式左边乘上 $1$ ，右边乘上 $aa^{-1}$ ： $x/a \times 1 \equiv x/a\times aa^{-1} \pmod p$ （同余式可以逐项相乘）
所以， $x/a\equiv xa^{-1} \pmod p$

同余式还有很多其他的性质，可以自行探索。

求逆元

拓展欧几里得法

算法介绍：拓展欧几里得算法

拓展欧几里得算法可以用来解同余方程。可以 $O(\log n)$ 求出单个数的逆元。

解方程： $ax\equiv 1 \pmod p$ 。
转化为 $ax + py = 1$ ，方程有解的条件为 $\gcd(a,p) \mid 1$ ，即 $\gcd(a,p)=1$ ， $a$ 和 $p$ 互质。
此时方程所有的解为 $x_0 + kp/\gcd(a,p) = x_0 + kp (k \in \Z)$ 。注意到所有的解 $x \equiv x_0 \pmod p$ ，故该线性同余方程只有一个解。（我们讨论的是在一个模剩余系中的解）。

综上我们得到了一条乘法逆元的重要性质。

乘法逆元性质 1
当且仅当 $a$ 与 $p$ 互质时， $a$ 在模 $p$ 意义下的乘法逆元 $a^{-1}$ 存在，且在模剩余系意义下有且仅有一个。

需要注意的是，不要学了逆元就遇到除法就开求逆元，先注意一下模数是不是一个素数。如果模数不是素数，那么一般来说，这题就不是要用逆元求的。（为了保证所有逆元存在，题目一般设置模数为素数）

int exgcd(int a,int b,int& x,int& y){
    if(!b){x=1,y=0;return a;}
    int g=exgcd(b,a%b,x,y);
    swap(x,y);
    y-=x*(a/b);
    return g;
}
int inv(int a,int p){ // 求 a 在模 p 意义下的逆元
    if(p%a==0)return -1;
    int x,y;
    exgcd(a,p,x,y);
    return (x+p)%p; // 保证是正数
}

线性求 1~n 逆元

在题目里，有时候需要用 $1\sim n$ 之间所有数的逆元，如果每一个都用上面的方法算的话，复杂度为 $O(n\log n)$ 。事实上，有一种方法，可以在 $O(n)$ 复杂度内求出 $1\sim n$ 的所有逆元。这用到的是另一个重要性质：

乘法逆元性质 2

$x^{-1} \equiv \left\{ \begin{aligned} &1, & x=1\\ &-\bigg\lfloor \dfrac{p}{x} \bigg\rfloor (p \bmod x)^{-1}, &\text{otherwise}\\ \end{aligned} \right. \pmod p$

我们来证明一下：

首先 $1^{-1} \equiv 1 \pmod p$ 。

对于求 $x^{-1}$ 其他情况，不妨令 $a = \bigg\lfloor \dfrac{p}{x} \bigg\rfloor$ ， $b=p \bmod x$ 。
则 $ax+b = p$ ，即 $ax+b\equiv 0 \pmod p$ 。
两边同乘 $x^{-1}b^{-1}$ ，得 $ab^{-1}+x^{-1}\equiv 0 \pmod p$ 。
移项，得 $x^{-1}\equiv -ab^{-1} \pmod p$ ，即 $x^{-1}\equiv-\bigg\lfloor \dfrac{p}{x} \bigg\rfloor (p \bmod x)^{-1}\pmod p$

我们注意到 $p \bmod x$ 小于 $x$ ，这样就可以线性递推出所有数的逆元。代码见下。

洛谷P3811 【模板】乘法逆元

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int N = 3e6+6;

int inv[N];

int main(){
    int n,p;
    scanf("%d%d",&n,&p);
    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",inv[i]);
    }
    return 0;
}

线性求 n 个任意数的逆元

事实上，可以在线性复杂度内求解出 $n$ 个任意数的逆元。（复杂度为 $O(n+\log p)$ ， $p$ 为模数）

具体方法如下：

设这 $n$ 个数为 $a_1,a_2,\dots,a_n$ 。
分别求出前缀积 $s_1,s_2,\dots,s_n$ 。
求出 $s_n$ 逆元 $v_n$ 。（用拓展欧几里得法）
对于任意 $v_i$ ， $v_i=v_{i+1}a_{i+1}$ （因为乘上一个数之后被抵消了），求出所有的 $v_i$ 。
则对于任意数 $a_i$ ，

$a_i^{-1}=\left\{\begin{aligned}&v_1, & i=1\\&v_is_{i-1}, &\text{otherwise}\\\end{aligned}\right.$

综上，即可在 $O(n+\log p)$ 复杂度求出任意 $n$ 个数的逆元。

洛谷P5431 【模板】乘法逆元 2

#include<bits/stdc++.h>
using namespace std;

int read(){ // 本题卡常严重
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

using ll=long long;

const int N = 5e6+6;
int a[N],s[N],v[N];

int p;

int exgcd(int a,int b,int &x,int &y){
    if(b==0){x=1,y=0;return a;}
    int g = exgcd(b,a%b,x,y);
    swap(x,y);
    y-=x*(a/b);
    return g;
}


int main(){
    

    int n=read();
    p=read();
    int k=read();

    s[0]=1;
    for(int i=1;i<=n;i++){
        a[i]=read()%p;
        s[i]=(ll)s[i-1]*a[i]%p;
    }

    int x,y;
    exgcd(s[n],p,x,y);
    v[n] = (x+p)%p;

    for(int i=n-1;i>=1;i--)v[i]=(ll)v[i+1]*a[i+1]%p;

    int ans = 0;
    int mul = k;
    for(int i=1;i<=n;i++){
        int inv;

        if(i==1)inv=v[1];
        else inv=(ll)v[i]*s[i-1]%p;

        ans = (ans+(ll)mul*inv)%p;

        mul=(ll)mul*k%p;
    }

    printf("%d\n",ans);

    return 0;
}