【模板】乘法逆元
题目背景
这是一道模板题
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入输出格式
输入格式:
一行n,p
输出格式:
n行,第i行表示i在模p意义下的逆元。
输入输出样例
输入样例#1:
10 13
输出样例#1:
1
7
9
10
8
11
2
5
3
4
分析:有一个递推式,不会证,ny[i]=(p-p/i)*ny[p%i]
代码
#include <cstdio>
#define N 3000005
#define ll long long
using namespace std;
ll a[N],p;
int n;
int main()
{
scanf("%d%lld",&n,&p);
a[]=;
printf("1\n");
for (int i=;i<=n;i++)
{
a[i]=(p-p/i)*a[p%i]%p;
printf("%lld\n",a[i]);
}
}