乘法逆元 [数学]

定义

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

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

常见求逆元的方法

1.拓展欧几里得求逆元

ps必须 $a, p$ 互质

复杂度 $l o g p$

#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)$

#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)$ 逆元

这里证明一并放到乘法逆元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;
}