原题链接

题解

由于时间限制过于严苛，遂采用线性递推方式
\(p=k·i+b\) ， \((1\leqslant b <r<p)\)
\(k·i+b=0\) \((mod\ p)\)
同时乘上 \(i^{-1}\ b^{-1}\)
\(k·b^{-1}+i^{-1}=0\ (mod\ p)\)
\(i^{-1}=-k·b^{-1}\ (mod\ p)\)
\(i^{-1}=(-[\frac{p}{i}]+p)+(p\ mod\ i)^{-1}\)

code,不优化过不了

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll inv[3000005] = {0};

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    ll n, p;
    read(n); read(p);
    inv[1] = 1;
    puts("1");
    for(int i = 2; i <= n; i++) {
        inv[i] = (-p/i + p) * inv[p % i] % p;  // Keep the original logic
        write(inv[i]);
        putchar('\n');
    }
    return 0;
}