一、逆元定义

二、求逆元的方法

1.扩展欧几里得(exgcd) 适用于单个查找或者模p很大的情况下 , p 不是质数的时候也可以使用

此处是线性同余方程(a*x≡b(modm))的特殊情况 (b=1)

所求解x=x*b/d%m，若要保证x是最小的正整数则x=(x%m+m)%m

 1 #include<iostream>
 2 using namespace std;
 3 //扩展欧几里得算法
 4 // 对任意一组 ax+by=m 存在一组x，y满足ax+by=gcd(a,b) 即m=gcd(a,b)
 5 int exgcd(int a, int b, int& x, int& y) {
 6     if (!b) {
 7         x = 1, y = 0;
 8         return a;
 9     }
10     int t = exgcd(b, a % b, y, x);
11     y = y - a / b * x;
12     return t;
13 }    
14 int main() {
15     int x, y;
16     int a, m;
17     cin >> a >> m;
18  
19     int d = exgcd(a, m, x, y);
20  
21      x = x / d % m;
22     x = (x % m + m) % m;
23     printf("%d", x);
24  
25     return 0;
26 }

2.快速幂 O(logk)

费马小定理:

将该公式进行变形则可得到

所以我们可以用快速幂来算出的值，这个数就是a的逆元

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 ll qmi(ll a, ll b,ll p) {
 5     ll res = 1;
 6  
 7     while (b) {
 8         if (b & 1) res = res * a % p;
 9         a = a * a % p;
10         b >>= 1;
11     }
12     return res;
13 }
14 int main() {
15     int a, b, p;
16     cin >> a >> b>>p;
17     ll x = qmi(a, b - 2,p); 
18  
19     return 0;
20 }

3.线性求逆元 (用于求一连串数字对于一个模p下的逆元) O(n)

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long LL;
 4 const int N = 3e6 + 10;
 5 int inv[N];
 6 int n, p;
 7 int main() {
 8     scanf("%d%d", &n, &p);
 9  
10     inv[1] = 1;
11  
12     for (int i = 2; i <= n; i++)
13         inv[i] = (LL)(p - p / i) * inv[p % i] % p;
14  
15  
16     return 0;
17 }

4.阶乘逆元 O(n) 只适用于模数为质数的情况

因此我们可以先求出n!然后进行递推来求出1->n!所有的逆元

递推式为:

 最后可以得到

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 3e6 + 10;
 5 ll a[N], b[N];
 6 ll n, p;
 7 ll qmi(ll a, ll b, ll p) {
 8     ll res = 1;
 9     while (b){
10         if (b & 1) res = res * a % p;
11         a = a * a % p;
12         b >>= 1;
13     }
14     return res;
15 }
16 int main() {
17     cin >>n >> p;
18  
19     a[0] = 1;
20     for (int i = 1; i <= n; i++)
21         a[i] = (a[i - 1] * i) % p;
22  
23         b[n] = qmi(a[n], p - 2, p);
24  
25  
26     for (int i = n - 1; i >= 1; i--) 
27         b[i] = (b[i + 1] * (i + 1)) % p;
28  
29     for (int i = 1; i <= n; i++)
30         cout << b[i] * a[i - 1]%p<<endl;
31  
32  
33  
34     return 0;
35 }