是什么
单位元
单位元是集合里的一种特别的元，与该集合里的运算（可理解为实数里的*，但并不局限于）有关。当它和其他元素结合时，并不会改变那些元素。
例如在加法运算中，某一元素 \(a\) 和另一元素 \(e\)，满足 \(a+e=a\)，那么 \(e\) 就是加法运算中的单位元，显然加法中 \(e=0\)，乘法中 \(e=1\)。
模乘下的单位元
在模 \(n\) 的乘法下，所有模 \(n\) 和 \(a\) 同余的数都可以表示为：
\[a \pmod{n}=kn+a,(k\in \mathbb{Z})
\]
令单位元为 \(e\)，然后将 \(a\) 与 \(e\) 进行模乘运算，得到：
\[\begin{align*}
a \pmod{n} \times e\pmod{n} &=(k_1n+a)(k_2n+e)\\
&=(k_1k_2n+k_1e+k_2a)n+ae
\end{align*}
\]
根据单位元的定义可知模乘运算下单位元 \(e=1\)。
逆元
逆元，是指一个可以取消另一给定元素运算的元素，也是在此运算下相结合后得到单位元的两个元素。
例如在加法运算中，某一元素 \(a\) 和另一元素 \(e\)，满足 \(a+e=0\)，那么 \(a\) 与 \(e\) 就互为逆元，显然加法中 \(e=-a\)，乘法中 \(e=\frac{1}{a}\)。
在模乘运算中，任意整数 \(a\pmod{n}\) 的逆元表示为: \(a^{-1}\pmod{n}\)
根据逆元的定义满足下列等式：\(aa^{-1} \equiv 1 \pmod{n}\)
裴蜀定理
设 \(a,b\) 是不为零的整数，那么对于任意整数 \(x,y\)，都有 \(\gcd(a,b)\mid ax+by\) 成立；而且，存在整数 \(x,y\)，使得 \(ax+by=\gcd(a,b)\) 成立。
逆元存在的必要条件
必须满足 \(\gcd(a,n)=1\)，即 \(a\) 与 \(n\) 互素。
根据裴蜀定理得：
\[ax+nk=\gcd(a,n)=1
\]
将此式对 \(n\) 取模，得到：
\[ax\equiv1 \pmod{n}
\]
这就意味着 \(x\) 为 \(a\) 在模 \(n\) 下的乘法逆元。
怎么求
费马小定理
给定素数 \(p\) 和正整数 \(a\)，一定满足 \(a^{p-1}\equiv 1\pmod{p}\)。
再经变形可得 \(aa^{p-2}\equiv 1\pmod{p}\)。
由此可知 \(a^{p-2}\pmod{p}\) 为 \(a\) 的逆元。
关于 \(a^{p-2}\) 用快速幂求得即可。
对应代码：
#include
using namespace std;
int a,b;
int ans=1;
void quick(int a,int k){
int base=a;
while(k){
if(k&1){
ans=ans*base;
ans%=b;
}
base=base*base%b;
k>>=1;
}
}
signed main(){
cin>>a>>b;
quick(a,b-2);
cout< return 0; } 拓展欧几里得算法 exgcd 给定正整数 \(a\) 和 \(b\)，求满足等式 \(ax+by=1\) 的 \(x\) 的最小正整数。如果不存在返回 \(-1\)。 先提取出 \(a\) 和 \(b\) 的最大公约数，即 \(g=\gcd(a,b)\)，则等式可以转化为： \[g(\frac{a}{g}x+\frac{b}{g}y)=1 \] 两数相乘结果为 \(1\)，要么都是 \(1\)，要么都是 \(-1\)，而最大公约数不可能为负数，所以 \(\gcd(a,b)=1\)，那么有解的条件就是 \(a\) 和 \(b\) 一定互素。 根据裴蜀定理可以把原式转化为：\(ax\equiv1 \pmod{b}\)，可以用费马小定理解得。 言归正传，回到 exgcd 上，我们对原始公式进行变形可得： \[\begin{align*} ax+by &=1\\ &=gcd(a,b)\\ &=gcd(b,a\bmod b)\\ &=bx^{\prime}+(a\bmod b)y^{\prime}\\ &=bx^{\prime}+(a-b\lfloor \frac{a}{b} \rfloor)y^{\prime}\\ &=ay^{\prime}+b(x^{\prime}-\lfloor \frac{a}{b} \rfloor y^{\prime}) \end{align*} \] 这是个递推式，我们可以递归求解，什么时候递归结束呢。 欧几里得算法计算两个互质的数到 \(gcd(1,0)\) 将返回，此时式子为 \[gcd(1,0)=ax+by=1=1\times x+0\times y \] 此时 \(x\) 为 \(1\)，\(y\) 为任意值。 对应代码： #include using namespace std; int a,b; int x,y; void exgcd(int a,int b){ if(b==0){ x=1; y=0; return; } exgcd(b,a%b); int t=x; x=y; y=t-a/b*y; return; } signed main(){ cin>>a>>b; exgcd(a,b); cout< return 0; } 逆元的应用 组合数 根据组合数计算公式：\(C_n^{m}=\frac{n!}{m!(n-m)!}\) 要计算阶乘然后除阶乘，但是除法不满足模运算，而逆元相当于倒数，用逆元阶乘来实现除法。 阶乘：\(fac[i]=fac[i-1]*i\) 阶乘逆元：\(\frac{1}{(n-1)!}=inv[i-1]=inv[i]*i=\frac{1}{n!}\times n\) 原理：\(fac[n]*inv[n]=1=n!\times \frac{1}{n!}\) 所以只需要求出 \(fac[n]\) 的逆元 \(inv[n]\) 即可。 #include using namespace std; const int N=2e5+10; const int mod=998244353; int a,b; int fac[N],inv[N]; int choose(int n,int m){ return fac[n]*inv[m]%mod*inv[n-m]%mod; } int quick(int a,int k){ int base=a%mod; int ans=1; while(k){ if(k&1){ ans=(ans*base)%mod; } base=(base*base)%mod; k>>=1; } return ans; } signed main(){ fac[0]=1; for(int i=1;i<=100005;i++){ fac[i]=fac[i-1]*i%mod; } inv[100005]=quick(fac[100005],mod-2); for(int i=100004;i>=0;i--){ inv[i]=inv[i+1]*(i+1)%mod; } cin>>a>>b; cout< return 0; }