洛谷 P3811：【模板】模意义下的乘法逆元
【题目来源】
https://www.luogu.com.cn/problem/P3811
【题目描述】
给定 n,p 求 1∼n 中所有整数在模 p 意义下的乘法逆元。
这里 a 模 p 的乘法逆元定义为 ax≡1(mod p) 的解。
【输入格式】
一行两个正整数 n,p。
【输出格式】
输出 n 行，第 i 行表示 i 在模 p 下的乘法逆元。
【输入样例】
10 13
【输出样例】
1
7
9
10
8
11
2
5
3
4
【说明/提示】
1≤n≤3×10^6，n<p<20000528。
输入保证 p 为质数。
【算法分析】
● 如果 ax≡1(mod b)，则称 x 为 a mod b 的乘法逆元。
● 在模 p 运算中，将负数 x 转换为对应的正数，执行 (x % p + p) % p 操作即可。
#include <bits/stdc++.h>
using namespace std;int normalize(int x,int p) {return (x%p+p)%p;
}int main() {int x,p;cin>>x>>p;cout<<normalize(x,p)<<endl;return 0;
}/*
in:-22 7
out:6
*/● 线性时间预处理 1 到 n 的模 p 逆元的理论证明
定理：inv[i]=(p-(p/i)*inv[p%i]%p)%p;
证明：设 k=p/i，r=p%i，则有 p=k*i+r
两边模 p 得：k*i+r≡0 (mod p) → i≡-r/k (mod p)
因此 inv[i]≡-k*inv[r] (mod p)。之后，将其调整为对应正数得证。【算法代码：100分代码】
● 在 C++ 中，若输入数据个数大于 10^5 时，推荐使用 scanf 而不是 cin 输入数据。这是因为 scanf 通常比 cin 更快。详见：https://blog.csdn.net/hnjzsyjyj/article/details/145618674
● 如下代码实现了线性时间预处理 1 到 n 的模 p 逆元，是数论中常用的高效算法。
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=3e6+5;
LL inv[N];int main() {LL n,p;scanf("%lld %lld",&n,&p);inv[1]=1;for(int i=2; i<=n; i++) {inv[i]=(p-(p/i)*inv[p%i]%p)%p;}for(int i=1; i<=n; i++) {printf("%lld\n",inv[i]);}return 0;
}/*
in:
10 13out:
1
7
9
10
8
11
2
5
3
4
*/
【算法代码：60分代码】
下面代码 TLE，只得 60 分，但也对理解逆元有很大参考价值。
#include <bits/stdc++.h>
using namespace std;typedef long long LL;LL exgcd(LL a,LL b,LL &x,LL &y) {if(b==0) {x=1,y=0;return a;}LL d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}LL modInverse(LL a, LL p) {LL x,y;LL d=exgcd(a,p,x,y);if(d!=1) return -1; //no inverse elementreturn (x%p+p)%p;
}int main() {int n,p;cin>>n>>p;for(int i=1; i<=n; i++) {LL inv=modInverse(i,p);if(inv==-1) cout<<-1<<endl;else cout<<inv<<endl;}return 0;
}/*
in:
10 13out:
1
7
9
10
8
11
2
5
3
4
*/
【参考文献】
https://blog.csdn.net/YSJ367635984/article/details/145540368
https://mp.weixin.qq.com/s/WZK9E0ODF1ciY8SfFtmXrQ
https://mp.weixin.qq.com/s/ue2wQsbKguCnfGINZXYW5g
https://www.luogu.com.cn/problem/P5431
https://www.cnblogs.com/yinyuqin/p/14773781.html