洛谷—— P3811 【模板】乘法逆元

https://www.luogu.org/problem/show?pid=3811

题目背景

这是一道模板题

题目描述

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

输入输出格式

输入格式：

一行n,p

输出格式：

n行,第i行表示i在模p意义下的逆元。

输入输出样例

输入样例#1：

10 13

输出样例#1：

说明

1 \leq n \leq 3 \times 10 ^ 6, n < p < 200005281≤n≤3×106,n<p<20000528

输入保证 pp 为质数。

线性求逆元、

 #include <cstdio>

 #define LL long long

 inline void read(LL &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 const int N(*1e6+);

 LL n,p,inv[N];

 int Presist()

 {

     read(n),read(p);

     inv[]=; puts("");

     for(int i=; i<=n; ++i)

         inv[i]=(LL)((p-p/i)*inv[p%i])%p,printf("%lld\n",inv[i]);

     return ;

 }

 int Aptal=Presist();

 int main(){;}

巴特西

洛谷—— P3811 【模板】乘法逆元

https://www.luogu.org/problem/show?pid=3811

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章