这是一道模板题。
给定正整数 nn 与 pp，求 1?n1?n 中的所有数在模 pp 意义下的乘法逆元。
Input
一行两个正整数 nn 与 pp
Output
nn 行，第 ii 行一个正整数，表示 ii 在模 pp 意义下的乘法逆元。
样例输入
10 13
样例输出
1
7
9
10
8
11
2
5
3
4思路一：费马小定理；
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
LL n,p;
LL pow_mod(LL x,LL n,LL mod){LL res=1;while(n){if(n&1) res=res*x%mod;x=x*x%mod;n=n>>1;}return res;
}
int main(){scanf("%lld%lld",&n,&p);for(LL i=1;i<=n;i++)printf("%lld\n",pow_mod(i,p-2,p));return 0;
} 思路二：递推求逆元；
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=3000005;
LL n,p,inv[maxn];
int main(){scanf("%lld%lld",&n,&p);inv[1]=1;for(int i=1;i<=n;i++){if(i!=1)inv[i]=(p-p/i)*inv[p%i]%p;printf("%lld\n",inv[i]);}return 0;
}