这道题是线性推逆元，O（n）才可以过。。。
扩欧单次logn，总复杂度是nlogn的
by zzy2333 @ 2019-03-26 19:20:08
~~刚学oi系列~~
by zzy2333 @ 2019-03-26 19:20:27
递推：
```cpp
inv[n] = (p-p/i)*inv[p%i]%p;
```
by NaCly_Fish @ 2019-03-26 19:22:54
@[NaCly_Fish](/space/show?uid=115864) 打错了，把inv[n]改成inv[i]
by NaCly_Fish @ 2019-03-26 19:23:19
orz orz
by Hydrogen_Helium @ 2019-03-26 19:25:31
@[氢氦](/space/show?uid=168322)
真正的线性推逆元：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N=20000529;
int n,p;
int inv[MAX_N];
signed main()
{
cin>>n>>p;
inv[1]=1;
for(int i=2;i<=n;i++)
{
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=1;i<=n;i++)printf("%lld\n",inv[i]);
return 0;
}
```
by Smile_Cindy @ 2019-03-26 19:48:33
有超时的，怎么办
```c
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,p,ans;
long long power(long long a,int b){
int ret=1;
while(b){
if(b&1){
ret=ret*a%p;
}
a=a*a%p;
b>>=1;
}
return ret;
}
int main(){
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++){
ans=power(i%p,p-2);
printf("%d\n",ans);
}
return 0;
}
```
by Dlive·Lx @ 2019-04-14 09:05:19
@[NaCly_Fish](/space/show?uid=115864) 大佬，请解释一下
by Dlive·Lx @ 2019-04-14 09:15:14
@[Dlive·Lx](/space/show?uid=94229) 您这还是n log n复杂度的啊。。 所以超时了
by NaCly_Fish @ 2019-04-14 09:46:27
@[NaCly_Fish](/space/show?uid=115864) 哦，我知道了。
by Dlive·Lx @ 2019-04-14 09:49:53