luogu3811【模板】乘法逆元

luogu3811【模板】乘法逆元

​​ 题目背景

这是一道模板题

题目描述

给定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 线性时间求逆元

设t=p/i,k=p%i

t*i+k=0%p;

-t*i=k%p;

两边同时除以i*k

-t*inv[k]=inv[i](mod p)

为了保证最小正逆元两边同时加p 然后再对p取mod即可

#include #define N 3300000int inv[N],n,p;int main(){ scanf("%d%d",&n,&p);inv[1]=1; for (int i=2;i<=n;++i) inv[i]=(long long)(p-p/i)*inv[p%i]%p; for (int i=1;i<=n;++i) printf("%d\n",inv[i]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。