题解

问题分析

题目要求计算在 $n$ 以内满足 $P(x) = m$ 的正整数 $x$ 的数量，其中 $P(x)$ 定义为满足 $1 < y < x$ 且 $y^3 \equiv 1 \pmod{x}$ 的 $y$ 的数量。

核心在于分析 $P(x)$ 的性质：

• 由中国剩余定理，若 $x$ 的素因子分解为 $x = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$，则同余方程 $y^3 \equiv 1 \pmod{x}$ 的解的数量是各素数幂 $p_i^{e_i}$ 上解的数量的乘积。
• $y=1$ 始终是解，但 $P(x)$ 仅计数 $1 < y < x$ 的解，因此 $P(x) = t - 1$（$t$ 为总解数，需减去 $y=1$ 的情况）。
• 素数幂 $p^e$ 上的解数：
  • 若 $p \equiv 2 \pmod{3}$ 或 $p=2$ 或 $p=3$ 且 $e=1$，解数为 $1$（仅 $y=1$）。
  • 若 $p \equiv 1 \pmod{3}$ 或 $p=3$ 且 $e \geq 2$，解数为 $3$（含 $y=1$ 和另外两个解）。

由此可得：$P(x) = 3^d - 1$，其中 $d$ 是 $x$ 的素因子分解中“解数为3的素数幂”的个数（即满足 $p \equiv 1 \pmod{3}$ 或 $p=3$ 且 $e \geq 2$ 的素数幂的个数）。若 $m+1$ 不是 $3$ 的幂，则答案为 $0$。

算法步骤

1. 判断 $m+1$ 是否为 $3$ 的幂：若不是，直接返回 $0$；若是，设 $3^d = m+1$，需统计 $x \leq n$ 中恰好含 $d$ 个“解数为3的素数幂”的数的数量。

2. 素数计数准备：

   • 用改进的筛法（类似 Meissel-Lehmer 算法）计算区间内素数总数（$\pi(n)$）和 $p \equiv 1 \pmod{3}$ 的素数数量，支持高效查询。

3. 深度优先搜索（DFS）计数：

   • 递归枚举 $d$ 个“解数为3的素数幂”（彼此不同的素数），并统计剩余因子为“解数为1的素数幂”的组合数，确保乘积 $\leq n$。
   • 累计所有符合条件的 $x$ 的数量。

代码解析

• 素数计数模块（build 函数）：预处理小范围（$\leq \sqrt{n}$）和大范围（$> \sqrt{n}$）的素数数量及 $p \equiv 1 \pmod{3}$ 的素数数量，用于快速查询。
• DFS 模块（dfs 函数）：递归枚举 $d$ 个目标素数幂，结合素数计数结果计算符合条件的 $x$ 的数量，处理素数幂的不同次幂情况。
• 主函数：判断 $m+1$ 是否为 $3$ 的幂，初始化参数后调用 DFS 统计答案。

复杂度分析

• 时间复杂度：依赖于素数计数的效率和 DFS 枚举的深度，对于 $n \leq 2 \times 10^{10}$，通过分块和优化筛法可将复杂度控制在 $O(n^{3/4} / \log n)$ 级别。
• 空间复杂度：$O(\sqrt{n})$，用于存储小范围素数计数结果和中间变量。

综上，该算法通过数论性质简化问题，结合高效素数计数和递归枚举，实现了对大规模数据的快速求解。