[模板]乘法逆元

定义

乘法逆元是一个十分有用的东西。 给定 q,x 求 x−1≡y(mod q) 就是说求 xy=1(mod q) ， y 的最小值

意义

在mod p意义下 xy=x×y−1 可以由此取整

求法

费马小定理

yq≡y(mod q) （ q 为质数）

求解

我们可以通过费马小定理，得： yq−1≡1(mod q) yq−2≡1y=y−1(mod q) 所以： y−1≡yq−2(mod q)

线性递推

f[i]=(p−p/i)f[i mod p]

int n,p,f[3000010]; int main() { n=read(); p=read(); printf("%d\n",f[1]=1); fr(i,2,n) printf("%d\n",f[i]=(ll)(p-p/i)*f[p%i]%p); rt 0; }

练手题

Luogu P3811 需要快速幂 注： 程序中 power(i,p−2,p)=ip−2 mod p

int n,p; int main() { n=read(); p=read(); fr(i,1,n) printf("%d\n",power(i,p-2,p)); rt 0; }