逆元的应用场景——模意义下的除法

  1. 在模意义下，加减乘必然都是可行的，(ab)%p=((a%p) (b%p))%p ;但是除法是不可行的，(a/b)%p (a%p)/b
  2. 假设有个值inv[b],(即), 满足a / b = a inv[b]，即我们就需要找到满足binv[b]%p=1的b；根据费马的定理，如果p是个质数，则有%p=1, 即inv[b]= ，因此这样我们就可以把模意义下的除法改为乘法，需要用到快速幂（取模)

Code(求):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
const int p = 1e9 + 7;
i64 power_mod(i64 a, i64 b, i64 mod){ //快速幂取模
	i64 res = 1;
	a = a % mod;
	while (b){
		if (b & 1)
			res = (res * a) % mod;
		b /= 2;
		a = (a * a) % mod;
	}
	return res;
}
signed main(){
	std::ios::sync_with_stdio(false);cin.tie(0);
	i64 a, b, ans;
	cin >> a >> b;
	i64 inv = power_mod(b, p - 2, p); //乘法逆元值b^(p-2)(mod p)
	ans = (a * inv) % p;
	return 0;
}
  1. 逆元的线性递推公式:当p为质数时，必然有inv[i]=inv[p%i]*(p-p/i)%p，可以在复杂度为O(n)的情况下求出1-n的逆元：
    1
    2
    3
    inv[1]=1;cout<<1<<endl;
    for(int i=2;i<=n;i++)
        inv[i]=inv[p%i]*(p-p/i)%p,cout<<inv[i]<<endl;