定义
若在\(\mod p\) 意义下，对于一个整数 \(a\) ,有 \(a*x\equiv 1(\mod p)\)，那么这个整数 \(x\) 即为 \(a\) 的乘法逆元，同时 \(a\) 也为 \(x\) 的乘法逆元。
充要条件
\(a\) 存在模 \(p\) 的乘法逆元的充要条件是
\(\gcd(a,p)=1\)，即 \(a\bot p\)。
应用
\(x\gets b\)的逆元
\(a/b\mod p\) 等同于求 \(a*x\mod p\)
证明&验证
\(x\gets b\) 的逆元
\(b*x\equiv1(\mod p)\)
可以认为 \(x\) 是 \(b\) 数论上的dao数
那么 \(a/b\mod p\) 可以转换为 \(a*x\mod p\)
\(a/b\mod p=m\) ......\(1\)式
\(1\) 式 \(*b\) 得
\(a\mod p=m*b\mod p\)
\(a\equiv m*b(\mod p)\)......\(2\)式
\(2\)式 \(*x\) 得
\(a*x\equiv m*b*x(\mod p)\)
\(\because b*x\equiv1(\mod p)\)
\(\therefore a*x\equiv m(\mod p)\)
综上，得证
费马小定理求解
假设 \(a\in\mathbb{N}\)，\(p\) 是素数
-
如果 \(a\) 是 \(p\) 的倍数，\(a^p\equiv a(\mod p)\)
-
如果 \(a\) 不是 \(p\) 的倍数，\(a^{p-1}\equiv 1(\mod p)\)
因为 \(a\bot p\) ，用第二条
\(a^{p-1}\equiv 1(\mod p)\) 转化变成
\(a*a^{p-2}\equiv 1(\mod p)\)
\(x=a^{p-2}\mod p\)
快速幂即可
typedef long long LL;
int QWQ(int a,int p){
int b=p-2,ans=1%p;
while(b){
if(b&1)ans=(LL)ans*a%p;
a=(LL)a*a%p;
b=b>>1;
}
return ans;
}
扩展欧几里得求解
\(a,b \in\mathbb{N}, a\bot b\) ，希望得到整数 \(x,y\)，
使得 \(ax+by=\gcd(a,b)\)
int exgcd(int a,int b,int &x,int &y){
if(b==0) { x=1, y=0; return a; }
int r=exgcd(b,a%b,x,y), t=y;
y=x-a/b*y, x=t;
return r;
}