题目背景

这是一道模板题

题目描述

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

输入输出格式

输入格式：

一行n,p

输出格式：

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

输入输出样例

输入样例#1：

10 13

输出样例#1：

179108112534

说明

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

输入保证 p p p 为质数。

思路

先扔个线性预处理求逆元，其他回头补QUQ

代码

线性预处理；

1 #include
      
        2 const int maxn=3e6+10; 3 int n,p; 4 int inv[maxn]={
    0,1}; 5 int main(){ 6     scanf("%d%d",&n,&p); 7     if(n>0) puts("1"); 8     for(int i=2;i<=n;i++){ 9         inv[i]=1ll*(p-p/i)*inv[p%i]%p;10         printf("%d\n",inv[i]);11     }12     return 0;13 }
      

 

不知道从哪里偷来的片段：

int FP(int x,int y) {    int ret=1;    while(y) {        if(y&1) ret=(1ll*ret*x)%p;        y>>=1,x=(1ll*x*x)%p;    }    return ret;}int IE(int x) {
    return FP(x,p-2);}