题解 | #【模板】乘法逆元#
【模板】乘法逆元
https://ac.nowcoder.com/acm/problem/229004
题意
给你一个整数和素数
，让你求所有整数在模
意义下的乘法逆元
思路
线性求乘法逆元
假设我们已知 的逆元，我们现在要求
也就是
的逆元，
已知 等于
,
那么说明 ，
经过移项就可以得到
代码
#include <bits/stdc++.h>
int main() {
int n, p; std::cin >> n >> p;
std::vector<int> inv(n + 1);
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = ((-1ll * inv[p % i] * (p / i)) % p + p) % p;
}
for (int i = 1; i <= n; ++i) {
// std::cout << inv[i] * i % p << ' ';
std::cout << inv[i] << '\n';
}
return 0;
}
查看9道真题和解析