题解 | 洛谷P3811 【模板】模意义下的乘法逆元 #

$[模板+线性逆元]$

两种求解逆元的方法：快速幂和扩展欧几里得算法，时间复杂度都为 $O(log_{2}^{p})$ ， $P$ 是模数

这道题目需要求从 $1$ 到 $n$ 所有数对 $pP$ 的乘法逆元，时间复杂度为 $O(n\times log_{2}^{p})$ ，最坏情况是 $O(3\times 10^{6}\times log_{2}^{20000528})\approx 6.4\times 10^{7}$ ，给卡超时了

正确的解法是线性逆元，在 $O(n)$ 的时间复杂度求出从 $1$ 到 $n$ 所有数对 $p$ 的乘法逆元，该方法是线性从前推后，所以与时间复杂度与 $p$ 没有关系

现在如何求 $niyuan[i]$ ?

设 $p=k\times i +r$

$k\times i +r\equiv 0\ (mod\ p)$ ，两边同时乘以 $niyuan[i]\times niyuan[r]$ ，则 $(k\times i +r) \times niyuan[i] \times niyuan[r] \equiv 0 \ (mod\ p)$

即 $k\times i \times niyuan[i] \times niyuan[r] + r \times niyuan[i] \times niyuan[r] \equiv 0 \ (mod\ p)$ ，化简为 $k \times niyuan[r] + niyuan[i] \equiv 0 \ (mod\ p)$

所以 $k \times niyuan[r] + niyuan[i] \equiv 0 \ (mod\ p)$

因为 $k = \lfloor \frac{p}{i} \rfloor$ ， $r = p\ mod\ r$

所以 $niyuan[i]\equiv- \lfloor\frac{p}{i} \rfloor \times niyuan[p\ \%\ i]\ (mod\ p)$ ，因为为负数，所以 $niyuan[i]\equiv (p - \lfloor\frac{p}{i} \rfloor) \times niyuan[p\ \%\ i]\ (mod\ p)$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;

    int n, p; cin >> n >> p;
    vector<int> niyuan(n + 1);
    niyuan[1] = 1;
    for(int i = 2; i <= n; i ++) niyuan[i] = ((p - p / i) * niyuan[p % i]) % p;
    for(int i = 1; i <= n; i ++) cout << niyuan[i] << endl;
    return 0;
}