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

P3811 【模板】模意义下的乘法逆元 - 洛谷 | 计算机科学教育新生态

题目背景

这是一道模板题

题目描述

给定 n,p 求 1∼n 中所有整数在模 p 意义下的乘法逆元。
这里 a 模 p 的乘法逆元定义为 ax≡1 (mod p) 的解。

输入格式

一行两个正整数 n,p。

输出格式

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

输入输出样例

输入 #1

10 13

输出 #1

1
7
9
10
8
11
2
5
3
4

说明/提示

• 1≤n≤3×1e6
• n<p<20000528
• 输入保证 p 为质数。

思路：

代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<string> 
using namespace std;
typedef long long ll;
const ll N = 1e6*3+1;
ll inv[N];
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll n,p;cin >> n >> p;inv[1] = 1;for(ll i = 2 ; i <= n ; i++){inv[i] = (p-p/i)*inv[p%i] % p;}for(ll i = 1 ; i <= n ; i++)cout << inv[i] << '\n';return 0;
}