题解 P3811 【【模板】乘法逆元】

zcysky · 2017-07-13 16:28:39 · 题解

害怕 不懂为什么底下能扯到线性筛什么的……

普通球逆元就是naive的pow(x,mod-2)注意此时mod必须为质数

这题一下子叫你求这么多很明显不是这么做的嘛

逆元有线性递推的公式，推一下就好了呀。

#include<bits/stdc++.h>
#define N 3000010
typedef long long ll;
using namespace std;
int inv[N],n,p;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int main(){
    n=read();p=read();inv[1]=1;puts("1");
    for(int i=2;i<=n;i++){
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
        printf("%d\n",inv[i]);
    }
}