概念

若关于整数 \(a,b\) 的线性同余方程 \(ax≡1\pmod{b}\) 存在解，则将 \(x\) 称作 \(a \bmod b\) 的乘法逆元（简称逆元），记作 \(a^{-1} \pmod{b}\)，在不会引起误解时常记作 \(a^{-1}\)

当 \(b|a\)（整除）时，不存在 \(a\) 的逆元 \(a^{-1} \pmod{b}\)
特别的，有\(1^{-1}≡1 \pmod{b}\)
- 证明：对于整数 \(b\)，有 \(1 \times 1≡1 \pmod{b}\)，故 \(1 \bmod b\) 的逆元为 \(1\)

性质

若 \(n\) 为正整数，则 \(a^{-1}≡n+1 \pmod{2n+1}\)
- 证明：已知 \(2x≡1\pmod{2n+1}\)，设 \(2x=(2n+1)k+1\)，又因为 \(2x\) 为偶数，\(k\) 的最小整数解为 \(1\)，代入得 \(x=n+1\)
若 \(b\) 为质数，且 \(a<b\)，则 \(a^{-1}≡a^{b-2}\pmod{b}\)
- 证明：~~需要用到费马小定理，暂时不会，学了回来再写~~

求法

1. \(exgcd\)

详见 \(\huge{exgcd学习笔记}\)

例题：同余方程

时间复杂度 \(O(\log\max(a,b))\)

2.线性求 \(1\sim n\) 或单个数的逆元（递推/递归）

限制条件：\(b\) 为质数

证明：

设 \(k=\lfloor{\frac{b}{i}}\rfloor\)，\(r=b\bmod i\),则有：

\(b=k\times i+r≡0\pmod{b}\)

两边同时乘上 \(i^{-1}\times r^{-1}\) 得：

\(k\times r^{-1}+i^{-1}\pmod{b}\)

移项得 \(i^{-1}≡-k\times r^{-1}\pmod{b}\)

将 \(k=\lfloor{\frac{b}{i}}\rfloor\)，\(r=b\bmod i\) 代入得：

\(i^{-1}≡-\lfloor{\frac{b}{i}}\rfloor\times (b\bmod i)^{-1}\pmod{b}\)

考虑消除负数取模对答案的影响，故推出逆元：

\[i^{-1}=\begin{cases} 1&i=1\\ (b-\lfloor{\frac{b}{i}}\rfloor)\times (b\bmod i)^{-1}&i\neq 1\\ \end{cases} \]

递推求 \(1\sim n\) 的逆元，\(O(n)\) 预处理，\(O(1)\) 查询
递归求任意数的逆元，时间复杂度 \(O(n^{\frac{1}{3}})\)

例题

\(\huge{乘法逆元}\)

代码如下（递推）：

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,p,inv[10000010];
void niyuan(int n)
{
    inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=((p-p/i)*inv[p%i])%p;
}
signed main()
{
	#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    read(n),read(p);
    niyuan(n);
    for(int i=1;i<=n;i++)
        write(inv[i]),puts("");
}