非常想三种方法都用一下，于是rand()走起：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <ctime> using namespace std; int n, p, y, x; int inv[3000200]; void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 ^ 48); } void ex_gcd(int a, int b) { if (!b) { x = 1, y = 0; return; } ex_gcd(b, a % b); int t = x; x = y; y = t - a/b * y; return; } int fastpow(int a, int b) { int ans = 1; while (b) { if (b & 1) ans = (1LL * ans * a) % p; b >>= 1, a = (1LL * a * a) % p; } return ans; } int main() { srand(time(0)); scanf("%d%d", &n, &p); inv[1] = 1; for (register int i = 2, j = rand() % 30; i <= n; ++i, j = rand() % 30) if (j != 1 && j != 2) inv[i] = 1LL * inv[p % i] * (p - p / i) % p; else if (j == 1) ex_gcd(i, p), inv[i] = x, inv[i] = (inv[i] % p + p) % p; else if (j == 2) inv[i] = fastpow(i, p - 2); for (register int i = 1; i <= n; ++i) write(inv[i]), putchar(' '); return 0; }