逆元

acwing：https://www.acwing.com/problem/content/878/

求逆元

#include 
using namespace std;
#define LL long long
LL n, a, p;
LL qmi(LL a, LL k, LL p){
	LL ans = 1;
	while (k){
		if (k & 1) ans = ans * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return ans;
}
//1.快速幂求逆元
LL inv(LL x){
	return qmi(x, mod - 2, mod);
}
//2.扩展欧几里得求逆元
//LL inv(LL a){
//	LL x, y;
//	exgcd(a, mod, x, y);
//	x = (x % mod + mod) % mod;
//	return x;
//}
//3.线性递推求逆元
//inv[1] = 1;
//for (int i = 2; i <= n; i ++ )
//	inv[i] = (p - p / i) * inv[p % i] % p;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++ ){
		cin >> a >> p;
		if (a % p == 0) cout << "impossible\n";
		else cout << inv(a, p) << "\n";
	}
	return 0;
}

luogu：https://www.luogu.com.cn/problem/P3811

给定 \(n\)，\(p\) 求 1 ~ \(n\) 中所有整数在模 \(p\) 意义下的乘法逆元。

#include 
using namespace std;
#define LL long long
const int N = 3e6 + 10;
LL n, p, inv[N];
int main(){
	cin >> n >> p;
	inv[1] = 1;
	cout << inv[1] << "\n";
	for (int i = 2; i <= n; i ++ ){
		inv[i] = (p - p / i) * inv[p % i] % p;
		cout << inv[i] << "\n";
	}
	return 0;
}

luogu：https://www.luogu.com.cn/problem/P5431

给定 \(n\) 个正整数 \(a_i\)，求它们在模 \(p\) 意义下的乘法逆元，给定常数 \(k\)，输出 \(\sum_{i = 1}^n \frac{k^i}{a_i}\)，答案对 \(p\) 取模。
题目卡常，要快读。

思路：

定义 \(s = \prod_{i = 1}^n\)。原式就转化为 \(\frac{k^i * \frac{s}{a_i}}{s}\)。
预处理一下前缀积和后缀积，就可以求了。

#include 
using namespace std;
#define LL long long
const int N = 5e6 + 10;
LL ans, n, p, k, a[N], pre[N], suf[N];
inline LL read(){
	LL s = 0, w = 1;
	char ch = getchar();
	while ( ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar();}
	while ( ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
LL qmi(LL a, LL k, LL p){
	LL ans = 1;
	while (k){
		if (k & 1) ans = ans * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return ans;
}
LL inv(LL x){//快速幂求逆元
	return qmi(x, p - 2, p);
}
int main(){
	n = read(), p = read(), k = read();
	pre[0] = 1, suf[n + 1] = 1;
	for (int i = 1; i <= n; i ++ ){
		a[i] = read();
		pre[i] = pre[i - 1] * a[i] % p;
	}
	for (int i = n; i >= 1; i -- )
		suf[i] = suf[i + 1] * a[i] % p;
	for (LL i = 1, j = k; i <= n; i ++, j = j * k % p )
		ans = (ans + ( (j * pre[i - 1] % p) * suf[i + 1]) % p ) % p;
	cout << ( ans * inv(pre[n]) ) % p << "\n";
	return 0;
}

应用：
2021 CCPC 威海站：