题目背景

这是一道模板题

题目描述

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

输入输出格式

输入格式:

一行n,p

输出格式:

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

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

线性时间求逆元

设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即可

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论