本博客部分摘自 hwim
定义
乘法逆元的定义：若存在正整数a,b,p, 满足ab = 1(mod p), 则称a 是b 的乘法逆元, 或称b 是a 的乘法逆元。b ≡ a-1 (mod p)，a ≡ b-1 (mod p)
比如说, 在模7 意义下,3 的乘法逆元是5, 也可以说模7 意义下5的乘法逆元是3。模13意义下5的逆元是8
存在性
和同余方程很相似，在同余方程中
ab ≡ 1(mod p)
若a 与p 互质, 则一定存在一个正整数解b, 满足b < p，若a 与p 不互质, 则一定不存在正整数解b.
所以逆元要求a与p互质
求法
求逆元有三种求法，
1、扩展欧几里得
扩展欧几里得可以用来求这样的一组解的：ax+by = gcd(a,b)，求x和y
逆元，求这样的一个解：ax ≡ 1 (mod b)，
我们变一下式子
ax+by = gcd(a,b)，变成 ax+by = c 求一个数等于c
ax ≡ 1 (mod b)，变成 ax-by = 1 如果将y看成负的，ax+by = 1
那么，就可以用exgcd求了。
code：
#include<cstdio> int exgcd(int a,int b,int &x,int &y)
{
if (b==)
{
x = ;
y = ;
return a;
}
int r = exgcd(b,a%b,x,y);
int tmp = x;
x = y;
y = tmp-a/b*y;
return r;
} int main()
{
//gcd(a,p)==1
int a,p,r,x,y;
while (scanf("%d%d",&a,&p)!=EOF)
{
r = exgcd(a,p,x,y);
printf("%d",(x%p+p)%p);
}
return ;
} 扩展欧几里得求逆元
exgcd
2、线性求逆元
ab = 1(mod p)，求b
p%a = p-(p/a)*a;c++向下取整
那么(p/a)*a = p-(p%a);
(p/a)*a = -(p%a);在模p意义下p可以约掉
a = -(p%a)/(p/a);换一下位置
a-1 = -(p%a)-1*(p/a);
a-1可以用(p%a)-1推出，所以就可以用递推式来推出1到a的所有数的逆元。
code
求一个数的逆元
int INV(int a)//线性求a的逆元
{
if(a==) return ;
return ((-(p/a)*INV(p%a))%p);
}
求1-n的逆元
int inv[MAXN];
void INV(int a,int p)
{
inv[] = ;
for (int i=; i<=a; ++i)
inv[i] = (-(p/i))*inv[p%i]%p;
}
线性求逆元1
3、欧拉函数求逆元
欧拉定理：aφ(p) ≡ 1(mod p)（不会证，逃
对于任意互质的a,p 恒成立。
欧拉定理用来求逆元用的是欧拉定理的一个推论
a*aφ(p)-1 ≡ 1(mod p)
仔细观察，a*b ≡ 1(mod p)，在这里的b不就是上面的aφ(p)-1吗？，所以求出aφ(p)-1就好了。
所以我们用快速幂就可以求出乘法逆元了。
这个方法它需要多算一个欧拉函数，代码这里不再给出。
这里给出求欧拉函数O(根n)的做法
不懂欧拉的戳这里11101001
int getphi(int x){
int ret=;
for(int i=;prime[i]*prime[i]<=x;i++){
if(x%prime[i]==)
{
ret*=prime[i]-;
x/=prime[i];
while(x%prime[i]==)
x/=prime[i],ret*=prime[i];
}
}
if(x>) ret*=x-;
return ret;
}
V欧拉
应用
我们知道(a+b)%p = (a%p+b%p)%p
(a*b)%p = (a%p)*(b%p)%p
求(a/b)%p时，可能会因为a是一个很大的数，不能直接算出来，也无法像上面一样分解。
我们可以通过求b关于p的乘法逆元k，k ≡ b-1 (mod p) ，将a乘上k再模p，即(a*k) mod p。其结果与(a/b) mod p等价。
然后这就成了求a*k%p，然后就可以用那两个公式了。