洛谷P3811 【模板】模意义下的乘法逆元

题目背景

这是一道模板题

题目描述

给定 n,p 求  中所有整数在模 p 意义下的乘法逆元。

这里 a 模 p 的乘法逆元定义为  的解。

输入格式

一行两个正整数 n,p。

输出格式

输出 n 行，第 i 行表示 i 在模 p 下的乘法逆元。

输入输出样例

输入 #1
10 13

输出 #1
1
7
9
10
8
11
2
5
3
4

说明/提示

，。

输入保证 p 为质数。

思路分析

线性求逆元

        (p>x)

令

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=3e6+5;
ll n,p,inv[N];
int main(){cin>>n>>p;inv[1]=1;cout<<1<<"\n";for(ll i=2;i<=n;i++){inv[i]=-(p/i)*inv[p%i];inv[i]=(inv[i]%p+p)%p;cout<<inv[i]<<"\n";}return 0;
}