题意分析

我们要计算不超过 $n$ 的质数（$p>1$）中，对每个余数 $r=0,1,\dots,m-1$，满足 $p \bmod m = r$ 的质数个数。

$m \le 12$ 很小，但 $n$ 可达 $3\times 10^{10}$。

关键点

• 模 $m$ 余 $0$ 的质数：只有 $m$ 本身（如果 $m$ 是质数），否则没有。
• 其他余数类中可能有多个质数。
• 需要高效的质数计数算法，并且要按余数分类。

算法选择

小范围 ($n \le 10^7$)

直接埃拉托色尼筛法，统计每个余数类的质数个数。
复杂度 $O(n \log \log n)$。

大范围 ($n \le 3\times 10^{10}$)

需要用亚线性质数计数法，并且要按模 $m$ 分类。

这里适合用 Lucy_Hedgehog 筛法（DP 质数计数） 的推广，同时维护 $m$ 个余数类的计数。

推广的 Lucy_Hedgehog 方法

设 $g_r(v, k)$ 表示 $[2, v]$ 中，模 $m$ 余 $r$ 的质数或最小质因子 $> p_k$ 的数的个数。

初始时（$k=0$，即最小质因子 $\ge 2$）： $ g_r(v, 0) = \text{在 } [2, v] \text{ 中模 } m \text{ 余 } r \text{ 的整数个数} $ 注意要去掉 $1$，并且 $2$ 要算入对应余数类。

然后从小到大枚举质数 $p$ 进行筛除：

对于每个 $r = 0,1,\dots,m-1$： $ g_r(v, k) = g_r(v, k-1) - \sum_{\substack{p = p_k \\ p^2 \le v}} \left[ g_{r\cdot p^{-1} \bmod m}\left( \frac{v}{p}, k-1 \right) - g_{r\cdot p^{-1} \bmod m}(p-1, k-1) \right] $ 这里 $r\cdot p^{-1} \bmod m$ 是 $r$ 乘上 $p$ 模 $m$ 的逆元，因为我们要“回退” $p$ 的乘法效应。

更简单的理解：
当我们用 $p$ 筛时，被筛掉的数是 $p \times t$，其中 $t$ 的最小质因子 $\ge p$。
如果 $p \times t \equiv r \pmod{m}$，则 $t \equiv r \cdot p^{-1} \pmod{m}$。
所以要从余数 $r$ 中减去余数为 $r\cdot p^{-1} \bmod m$ 的 $t$ 的计数（去掉 $t < p$ 的部分，因为那些 $t$ 的最小质因子 $< p$，之前已被筛过）。

算法步骤

1. 预处理 $\sqrt{n}$ 以内的质数。
2. 初始化 $g_r[v] = \lfloor (v - r + m)/m \rfloor$（$[1, v]$ 中模 $m$ 余 $r$ 的整数个数），然后调整去掉 $1$ 的影响（如果 $r=1$ 则减 1）。
3. 对每个质数 $p$（从小到大），从大到小更新 $g_r[v]$（数论分块枚举 $v$）。
4. 最终 $g_r[n]$ 就是模 $m$ 余 $r$ 的质数个数。

样例验证

样例 1：$n=7, m=3$

• 余 0：$\{3\}$ → 1
• 余 1：$\{7\}$ → 1
• 余 2：$\{2,5\}$ → 2

输出：

1
1
2

样例 2：$n=100000, m=6$

输出：

0
4784
1
1
0
4806

验证：

• 余 0：无（6 不是质数）
• 余 1：很多质数，如 7,13,... 共 4784 个
• 余 2：只有 2
• 余 3：只有 3
• 余 4：无（偶数且大于 2）
• 余 5：很多质数，如 5,11,... 共 4806 个

复杂度

• 时间复杂度：$O\left( \frac{m n^{3/4}}{\log n} \right)$
• 空间复杂度：$O(m \sqrt{n})$
• 在 $n=3\times 10^{10}, m\le 12$ 时可行

总结

这道题是按模分类的质数计数问题，通过推广 Lucy_Hedgehog 筛法，同时维护 $m$ 个余数类的计数，可以高效处理 $n$ 高达 $3\times 10^{10}$ 的情况。关键在于利用模 $m$ 的逆元来正确转移余数类的关系。