首先扩O：T了一个点（因为上界松），83分。

#include 
     
      using namespace std;int n, p;void exgcd(int a, int p, int &b, int &x){    if (p==0){        b=1, x=0;        return;    }     exgcd(p, a%p, b, x);    int tmp=b;    b=x;    x=tmp-a/p*x;    return;}int main(){    scanf("%d%d", &n, &p);    int x, y;    for (int i=1; i<=n; ++i){        exgcd(i, p, x, y);        printf("%d\n", (x+p)%p);    }    return 0;}
     

然后费马，事实证明果然更慢，上界很紧。

#include 
     
      using namespace std;int n, p;int expower(int a, int pow, int mod){    int ans=1;    while (pow){        if (pow&1) ans=1LL*ans*a%mod;        a=1LL*a*a%mod;        pow>>=1;    }    return ans;}int main(){    scanf("%d%d", &n, &p);    for (int i=1; i<=n; ++i){        printf("%d\n", expower(i, p-2, p));    }    return 0;}
     

正解：首先$1^{-1} \equiv 1 \pmod p$

我们设：$p = k\cdot i + r,~r < i,~1 < i < p$

将其放在模p意义下：$k\cdot i + r \equiv 0 \pmod p$

两边同乘i^-1，r^-1就会得到：

$\begin{eqnarray*} k\cdot r^{-1} + i^{-1} &\equiv& 0 &\pmod p\\ i^{-1} &\equiv& -k\cdot r^{-1} &\pmod p\\ i^{-1} &\equiv& -\left\lfloor\frac{p}{i}\right\rfloor\cdot \left(p\bmod i\right)^{-1} &\pmod p\ \end{eqnarray*}$

于是核心代码就一行: 

A[i] = -(p / i) * A[p % i];

我的代码：

注意：有可能是负数

#include 
     
      using namespace std;const int maxn=3000000;int n, p, a[maxn];int main(){    scanf("%d%d", &n, &p);    a[1]=1;    printf("%d\n", a[1]);    for (int i=2; i<=n; ++i){        a[i]=(1LL*-(p/i)*a[p%i])%p;        a[i]=(a[i]+p)%p;        printf("%d\n", a[i]);    }    return 0;}