洛谷:P3811 【模板】乘法逆元 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
推导过程
保证 模数P 为一个质数。

代码 / code
/*Copyright (C) Eriktse 2022*/ #include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 3e6 + 9; int inv[maxn]; void initInv(int N, int P,int a[])//a[]用于接收并操作inv数组 { a[0] = a[1] = 1;//初始化 for(int i = 2;i <= N; ++ i)a[i] = (P - P / i) * a[P % i] % P; } signed main() { int N, P;cin >> N >> P; initInv(N, P, inv); for(int i = 1;i <= N; ++ i)printf("%lld\n",inv[i]); return 0; }
Comments NOTHING