定义

逆元素是指一个可以取消另一给定元素运算的元素
—百度百科

简单说 就是 a ∗ a − 1 = 1 a * a^{-1} = 1 a∗a−1=1 一样 在模 意义下有更多性质

常见求逆元的方法

1.拓展欧几里得求逆元

ps必须 a , p a,p a,p互质


复杂度 l o g p log p logp

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 10;
long long n, m;

long long exgcd(long long a, long long b, long long &x, long long &y) {
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

signed main() {
	ios::sync_with_stdio(0);
	long long a, b;
	cin >> a >> b;
	long long x = 0, y = 0;
	exgcd(a, b, x, y);
	cout << (x % b + b) % b << endl;
	return 0;
}

2.欧拉定理求逆元

也是 a p 必须互质

欧拉值 求法只要按照 公式直接出就好

复杂度 l o g ( p h i ( p ) ) + s q r t ( n ) log(phi(p)) + sqrt(n) log(phi(p))+sqrt(n)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 10;
long long n, m;

long long pow_mod(long long a, long long b, long long p) {
	long long res = 1;
	for(; b; b >>= 1) {
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}

long long phi(long long x, long long p) {
	long long res = x, tmp = x;
	for(int i = 2; i * i <= tmp; i ++) {
		if(x % i == 0) {
			res = (res / i) % p * ((i - 1 % p)) % p;
			while(x % i == 0) x /= i;
		}
	}
	if(x > 1) res = (res / x) % p * ((x - 1) % p) % p;
	return res;
} // 一般欧拉值 也不太可能比p大 板子就写下吧 一般也不需要 

long long phi(long long x) {
	long long res = x, tmp = x;
	for(int i = 2; i * i <= tmp; i ++) {
		if(x % i == 0) {
			res = res / i * (i - 1);
			while(x % i == 0) x /= i;
		}
	}
	if(x > 1) res = res / x * (x - 1);
	return res;
}
signed main(){
	cin >> a >> b;
	long long tmp = phi(b) - 1;
	cout << pow_mod(a, tmp, b) << endl; 
	return 0;
}

3.费马小定理求逆元

只要p 是质数 就行 不要求互质
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
long long n, m;

long long pow_mod(long long a, long long b, long long p) {
	long long res = 1;
	for(; b; b >>= 1) {
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}

const int p = 19260817;
template<typename T>
inline void read(T &x) {
	x = 0;
	char ch = getchar();
	bool f = false;
	while(!isdigit(ch)) {
		f |= (ch == '-');
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		x %= p;
		ch = getchar();
	}
	x = f ? -x : x;
}

signed main() {
	long long a, b;
	read(a), read(b);
	if(!b) puts("Angry!");
	else cout << a * pow_mod(b, p - 2, p) % p << endl;
	return 0;
}

线性求逆元

也算是 打表 不过之后我们通过类似 阶乘逆元的方式 可以 看出 前缀积的逆元就是逆元的前缀积(之后细讲)

线性求逆元模板

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 10;
int n, m;

long long pow_mod(long long a, long long b, long long p) {
	long long res = 1;
	for(; b; b >>= 1) {
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}

int inv[maxn], p;

signed main() {
	scanf("%d %d", &n, &p);
	inv[1] = 1;
	cout << inv[1] << endl;
	for(int i = 2; i <= n; i ++) {
		inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
		printf("%d\n", inv[i]);
	}
	return 0;
}

阶乘 O ( n ) O(n) O(n) 逆元

这里 证明 一并放到 乘法逆元2 中

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 10;
long long n, m;

long long pow_mod(long long a, long long b, long long p) {
	long long res = 1;
	for(; b; b >>= 1) {
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}

long long inv[maxn], p;
long long f[maxn], c[maxn];

signed main() {
	scanf("%lld %lld", &n, &p);
	c[1] = c[0] = 1;
	for(int i = 2; i <= n; i ++) 
		c[i] = c[i - 1] * i % p;
	f[n] = pow_mod(c[n], p - 2, p);
	
	for(int i = n - 1; i >= 1; i --) {
		f[i] = f[i + 1] * (i + 1) % p;
	}
	
	for(int i = 1; i <= n; i ++) 
		printf("%lld\n", f[i] * c[i - 1] % p);
	return 0;
}

乘法逆元2


注释部分T了 2333

#include <bits/stdc++.h>
using namespace std;
int p, n, k;
const int maxn = 5e6 + 10;

template<typename T>
inline void read(T &x) {
	x = 0;
	char ch = getchar();
	bool f = false;
	while(!isdigit(ch)) {
		f |= (ch == '-');
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = f ? -x : x;
}

long long pow_mod(long long a, long long b, long long p) {
	long long res = 1;
	for(; b; b >>= 1) {
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}

int b[maxn], s[maxn], a[maxn];

int main() {
	read(n), read(p), read(k);
	int ans = 0;
// for(int i = 1, a; i <= n; i ++) {
// read(a);
// ans = (1ll * ans + pow_mod(k, i, p) * pow_mod(a, p - 2, p)) % p ;
// }
// printf("%d\n", ans);
	s[0] = 1;
	b[n + 1] = 1;
	for(int i = 1; i <= n; i ++) {
		read(a[i]);
		s[i] = 1ll * s[i - 1] * a[i] % p;
	}
	b[n + 1] = pow_mod(s[n], p - 2, p);
	for(int i = n; i >= 1; i --) {
		b[i] = 1ll * b[i + 1] * a[i] % p;
	}
	int tmpk = k;
	for(int i = 1; i <= n; i ++) {
		ans = (ans + (1ll * b[i + 1] * s[i - 1]) % p * tmpk) % p;
		tmpk = 1ll * tmpk * k % p;
	}
	printf("%d\n", ans);
	return 0;
}