原题链接：https://www.luogu.com.cn/problem/P3811
题意解读：逆元的模版题。
解题思路：
1、同余和模运算
同余定义：若整数 a 和 b 除以 m 的余数相同，称 a 与 b 模 m 同余，记为 a ≡ b (mod m)
模运算符号：a mod m表示 a 除以 m 的非负余数，结果范围是 0 <= a mod m < m（区别于 “同余” 的等价关系，这是一个求余数的运算，在C++中用%表示mod）。
模运算性质：
- 加法性质：(a + b) % m = (a % m + b % m) % m
- 减法性质：(a - b) % m = (a % m - b % m) % m
- 乘法性质：(a * b) % m = (a % m * b % m) % m
2、逆元
模运算的除法不直接成立，需通过 “乘法逆元” 转化为乘法（核心：将 (a / c) % m转化为(a * c-1) % m，其中 c-1是 c 的逆元）。
逆元定义：若c * c-1 ≡ 1（mod m），则称 c-1是 c 模 m 的乘法逆元（逆元唯一，且在 1 <= c-1 < m范围内）。
逆元存在条件：gcd(c, m) = 1（即 c 与 m 互质）。若 c 与 m 不互质，则 c 的逆元不存在，除法运算无意义。
3、逆元计算方法
方法1：扩展欧几里得算法
设a的逆元为x，根据a * x ≡ 1（mod m）得到ax + my = 1，只需要解此不定方程，x的最小正整数解就是逆元。
方法2：费马小定理
当p为质数时，根据费马小定理有ap-1 ≡ 1（mod p）,a * ap-2 ≡ 1（mod p)，a的逆元是ap-2，通过快速幂即可求解。
方法3：递推法
最常用的是线性递推求模质数下的逆元，适用于需要批量计算 1, 2, ..., n在模质数 p 下逆元的场景（时间复杂度 O(n)，效率极高）。这种方法仅适用于 p 是质数 且 1 <= a < p的情况（此时 a 与 p 互质，逆元必然存在）
设 p 是质数，a 是区间 1 <= a < p 中的整数，目标是求a-1 (mod p)（即 a 的逆元）。
基础关系：令 p = k * a + r，其中 k = ⌊p/a⌋ （商），r = p mod a（余数），满足 0 < r < a < p（因 a < p且 p 是质数，r != 0）。
模运算转化：对等式 p = k * a + r两边模 p，得：0 ≡ k * a + r (mod p)移项后：r ≡ -k * a (mod p)
两边乘逆元化简：两边同乘 r-1 * a-1（因 r < a < p) 且 p 是质数，r 和 a 的逆元均存在）：r * r-1 * a-1 ≡ -k * a * r-1 * a-1 (mod p)左边化简为 a-1，右边化简为-k * r-1，即：a-1 ≡ -k * r-1 (mod p)
代入 k 和 r 的表达式：因 k = ⌊p/a⌋，r = p mod a，故递推公式为：a-1 ≡ - ⌊p/a⌋ * (p mod a)-1 (mod p)
边界条件：当 a = 1时，显然 1 * 1-1 ≡ 1 \(mod p)，因此1-1=1
递推公式：设inv[a]表示a的逆元，inv[1] = 1，inv[a] = ((p - ⌊p/a⌋) * inv[p % a]) % p
100分代码：
#include <bits/stdc++.h>
using namespace std;const int N = 3000005;
int inv[N];
int n, p;int main()
{cin >> n >> p;inv[1] = 1;for(int i = 2; i <= n; i++){inv[i] = 1ll * (p - p / i) * inv[p % i] % p;}for(int i = 1; i <= n; i++) printf("%d\n", inv[i]);return 0;
}