https://www.luogu.com.cn/problem/P3811
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e6+5;
int n,p;
int inv[maxn]; //inv[i] 表示 i 模 p 的乘法逆元
void work()//求出 1-n 所有数在模 p 意义下的乘法逆元 要保证p是一个素数且 n<p
{
inv[1]=1;
for(int i=2;i<=n;i++)
{
inv[i]=(ll)-(p/i)*inv[p%i]%p;
if(inv[i]<0)
inv[i]+=p;
}
}
int main()
{
scanf("%d %d",&n,&p);
work();
for(int i=1;i<=n;i++)
printf("%d\n",inv[i]);
return 0;
}
csu_xiji
发布了609 篇原创文章 · 获赞 23 · 访问量 3万+
关注