题解：P3811 【模板】模意义下的乘法逆元

0Io_oI0 · 2025-05-17 22:26:03 · 题解

update on 2025.10.29：之前写得比较潦草，现在重新回来修改。

博客食用效果更佳：link。

定义

若 \gcd(a,m)=1，则存在 a'\in\mathbb{Z} ，使得 a\times a'\equiv 1\pmod m，a' 称为 a 对模 m 的数论倒数，或者称 a' 为模 m 的逆元。

接下来我要证明一件事情，我看很多题解里都没有证明，那就是题目让我们输出 1 到 n 这 n 个整数模 m 的数论倒数，但是对于每个数真的都有数论倒数吗？答案是肯定的，接下来来证明：

首先 \left\{1,2,\dots,m\right\} 为模 m 的完系，因为 \gcd(a,m)=1 所以 \left\{a,2a,\dots,ma\right\} 也为模 m 的完系，所以这里面一定存在某一项模 m 余 1 ，即存在 a'\in \left\{1,2,\dots,m\right\} 使得 a\times a'\equiv 1\pmod m。

解法

题目中说明了 p 是质数，但是我们需要知道适用于任何情况的解法，就是扩展欧几里得解法，等会我们会介绍，这里作者介绍线性递推解法。

我们设 k=[\frac{p}{i}],p=ki+q 。所以 ki+q\equiv0\pmod p，那么 k\times i\times (i^{-1}\times q^{-1})+q\times (i^{-1}\times q^{-1})\equiv0\pmod p，所以 k\times q^{-1}+i^{-1}\equiv0\pmod p，那么 i^{-1}\equiv-k\times q^{-1}\pmod p，也就是说 i^{-1}\equiv-[\frac{p}{i}]\times q^{-1}\pmod p，用这个结论我们就可以求出 1 到 p-1 的逆元了！

使用时我们调用 f_a 即可，如果 a>p 那么就调用 f_{a \bmod p}。

这里给出模板题目：link。

代码

#include<bits/stdc++.h>
#define int long long
int n,p,f[3000005];
signed main(){
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    cin>>n>>p;
    f[1]=1;
    cout<<f[1]<<"\n";
    for(int i=2;i<=n;i++){
        f[i]=(-p/i*f[p%i]%p+p)%p;
        cout<<f[i]<<"\n";
    }
    return 0;
}

代码中需要注意如果是负数那么我们需要给它加 p。

显然代码中一层循环，复杂度为 \mathcal{O(n)}。

线性递推的解法对于求解多个逆元显然很有效，但是对于单组逆元却显得有些多余，于是我们有求单组逆元的两种解法。

费马小定理

前面提到了对于 p 不为质数，我们可以使用扩展欧几里得算法来求解，在说这个之前我们先了解一种只能对于 p 为质数求解单组逆元的算法。

定理本身

对于质数 p 和整数 a，若 \gcd(p,a)=1，则 a^{p-1}\equiv 1\pmod p。

定理证明

众所周知，我们还有一个著名的基本数论定理：欧拉定理。

欧拉定理

对于正整数 a,m，若 \gcd(a,m)=1，则 a^{\varphi(m)}\equiv 1\pmod m。

其中 \varphi(m) 为欧拉函数，表示模 m 的缩系的元素个数，即小于等于 m 的正整数中与 m 互质的数的个数。

证明

引理：令 \left\{a_1,a_2,\dots,a_{\varphi(m)}\right\} 为模 m 的缩系，则对于正整数 x 满足 \gcd(x,m)=1，有 \left\{x\times a_1,x\times a_2,\dots,x\times a_{\varphi(m)}\right\} 也为模 m 的缩系。

引理证明：

正难则反，考虑使用反证法。

假设存在一个正整数 x 使得 \gcd(x,m)=1 且 x\times a_i\equiv x\times a_j\pmod m。

那么，由于 \gcd(x,m)=1 所以有 a_i\equiv a_j\pmod m 与 \left\{a_1,a_2,\dots,a_{\varphi(m)}\right\} 为模 m 的缩系矛盾！

故，原命题成立。

欧拉定理证明：

证明了引理以后，欧拉定理也就很好证明了。

由引理可得，设 \left\{x_1,x_2,\dots,x_{\varphi(m)}\right\} 为模 m 的缩系，则 \left\{a\times x_1,a\times x_2,\dots,a\times x_{\varphi(m)}\right\} 也为模 m 的缩系，所以这两个几何的所有元素的乘积在模 m 的意义下相等，也就是：

(a\times x_1)\times (a\times x_2)\times \cdots\times (a\times x_{\varphi(m)})\equiv x_1\times x_2\times \cdots\times x_{\varphi(m)}\pmod m

然后，由于 x_1\times x_2\times \cdots\times x_{\varphi(m)}\equiv 1\pmod m 于是我们有

a^{\varphi(m)}\equiv 1\pmod m

证毕！

与费马小定理的关系

很显然，欧拉定理就是费马小定理的加强版，易知 \varphi(p)=p-1 于是，如果我们证明了欧拉定理就相当于证明了费马小定理。

求解逆元

根据费马小定理我们有：

a^{p-1}\equiv 1\pmod p

即

a\times a^{p-2}\equiv 1\pmod p

由乘法逆元的定义可知

a'\equiv a^{p-2}\pmod p

于是，我们就得出了如何求出 a 关于 p 的乘法逆元。

代码实现

问题被我们转化为了求 a^{p-2}\bmod p 的值，很自然的想到了利用快速幂求解。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,p;
int powmod(int a,int b,int mod){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
signed main(){
    cin>>a>>p;
    cout<<powmod(a,p-2,p);
    return 0;
}

算法复杂度为 \mathcal{O(\log p)}。

扩展欧几里得

内容

在讲扩展欧几里得算法之前，我们先要引出一个著名数论定理 Bézout 定理，关于它我也有讲解，可以看这篇博客：link。

我们考虑不定方程 ax+by=\gcd(a,b) 的一组特解，我们可以采用递归的方法来求解，实际上这也就是扩展欧几里得算法：

显然当 b=0 时，有 \left\{\begin{matrix}x=1\\y=0\end{matrix}\right. 满足条件。
当 b\ne 0 时，我们根据欧几里得算法有 \gcd(a,b)=\gcd(b,a\bmod b) 于是，我们就有 (a\bmod b)y+bx=\gcd(b,a\bmod b) 又由于 (a\bmod b)y+bx=\left(a-b\times\lfloor\frac{a}{b}\rfloor\right)\times y+bx 将 \operatorname{RHS} 展开，合并同类项后有 (a\bmod b)y+bx=ay+b\times \left(x-\lfloor\frac{a}{b}\rfloor y\right) 于是，我们令 x_0=y,y_0=x-\lfloor \frac{a}{b}\rfloor y 就有 ax_0+by_0=\gcd(a,b)。

代码实现

根据上述内容，我们可以打出扩展欧几里得算法的代码：

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

功能介绍

以上函数的返回值为 \gcd(a,b)，注意到参数 x,y 均在前面加上了取地址符，表示在函数中可以改变 x 与 y 的值，而函数运行完成后 x 与 y 所保存的值就是 ax+by=\gcd(a,b) 的一组特解。

与乘法逆元的联系

扩展欧几里得定理一般处理线性同余方程，我在这篇博客中有介绍：link，这里求乘法逆元也就相当于求关于 x 的同余方程 a\times x\equiv 1\pmod b 的解。

由线性同余方程的性质可以得到，方程有解当且仅当 \gcd(a,b)=1 也就是说，如果 \gcd(a,b)>1 我们输出无解就可以了。

又由于方程可以写成 ax+by=1 的形式，于是我们使用扩展欧几里得算法，可以求出特解 x_0 然后 x_0\bmod b 就是 a 在模 b 意义下最小的乘法逆元了。

代码实现

根据前面的内容可以打出代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int exgcd(int a,int b,int&x,int&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-(a/b)*y;
    return d;
}
signed main(){
    cin>>a>>b;
    int x,y;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b;
    return 0;
}