题目解析 本题有两种方法可以解决，前者的切入点更平滑，后者更偏向于数学直觉一些。 方法一（并查集） 比较直接的一个想法，从 NNN 开始执行搜索，把 [2,N−1][2, N - 1][2,N−1] 中未加入集合且与当前元素不互质的元素加入集合 SSS。 那么显然我们的目标就是如何快速地找到与 NNN 不互质的元素集合 S′S'S′，对于 S′S'S′ 中的每个元素，再找到与其不互质的元素，以此类推。 由于本题中的操作具有传递性质：XXX 与 YYY 不互质；YYY 与 ZZZ 不互质，那么 XXX，YYY，ZZZ 都属于同一个集合。 我们可以从小到大考虑每个元素 XXX，令 XXX 的最小质因子 P(X)P(X)P(X)，那么有： 1. 若 XXX 为质数，显然集合中只有 XXX 本身。 2. 若 XXX 不为质数，那么显然我们将其拆分为 P(X)P(X)P(X) 与 XP(X)\dfrac{X}{P(X)}P(X)X ，那么二者所在的集合可以借助 XXX 合并起来。 我们将处理到元素 XXX 时，其所在的集合的大小设为 f(X)f(X)f(X)，那么对应的操作次数为 f(X)−1f(X) - 1f(X)−1。 所以我们可以预处理 3×1063 \times 10^63×106 中的所有元素，然后依次回答每个查询即可。 令 M=max⁡(Ni)M = \max(N_i)M=max(Ni )，此方法时间复杂度为 O(Mα(M)+Mlog⁡log⁡M+T)\mathrm{O}(M\alpha(M) + M\log{\log{M}} + T)O(Mα(M)+MloglogM+T)。 并查集每个操作平均时间复杂度为 α(M)\alpha(M)α(M)，其中 α\alphaα 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。 方法二（前缀和） 如果仔细分析最终集合 SSS 中的元素会发现，在当 NNN 不为素数时，所有素数 p(⌊N/2⌋<p<N)p(\lfloor N / 2 \rfloor \lt p \lt N)p(⌊N/2⌋<p<N) 都是无法加入到集合中的。其原因从上面的并查集解中不难发现，对于这样元素 ppp 是无法通过拆解 NNN 来使其合并到 NNN 所在的集合的。 我们令 f(N)f(N)f(N) 表示前 NNN 个元素中素数的数量，那么对于每个 NNN，若 NNN 为素数，操作次数为 000，否则为 N−(f(N)−f(⌊N2⌋)−2N - (f(N) - f(\lfloor \frac{N}{2} \rfloor) - 2N−(f(N)−f(⌊2N ⌋)−2。 那么我们在做完筛法后，使用前缀和计算出所有的 f(N)f(N)f(N) 即可。 令 M=max⁡(Ni)M = \max(N_i)M=max(Ni )，此方法时间复杂度为 O(Mlog⁡log⁡M+T)\mathrm{O}(M\log{\log{M}} + T)O(MloglogM+T)。 AC代码 方法一（并查集） 方法二（前缀和）

建议降 黄/橙。 分类讨论： 这个数是不是质数？是？那就没得操作了，直接输出 000。 如果不是质数，那他有没有为 222 的质因子？ 有：那就能把所有 2×i(2×i≤N)2\times i(2\times i \le N)2×i(2×i≤N) 的数都给加进这个集合内，然后所有 i(2×i≤N)i(2\times i \le N)i(2×i≤N) 也都进去了。 没有：那就把其中一个质因子 ×2\times 2×2 放进集合内，可以证明它必定小于 NNN。然后就和上面的一样了。 当 NNN 足够大时（N≥32N\ge 3^2N≥32 就行），显然不能进入集合的只有所有 >⌊N/2⌋\gt \lfloor N/2\rfloor>⌊N/2⌋ 的质数。显然这可以前缀和秒掉。 时间复杂度 O(Nln⁡ln⁡N+T)O(N\ln\ln N+T)O(NlnlnN+T)。

可用线性筛找所有素数，同时计算前缀和 pre[i]pre[i]pre[i] (表示前 iii 个数字里的素数数) 。 * 若 nnn 是素数，直接输出 000 即可。 * 若 nnn 非素数，显然要计算小于 nnn 且能与 nnn 合到同一集合的元素数。显然得排除在区间 [n/2,n][n / 2, n][n/2,n] 内的素数数 即用 n−2n - 2n−2 (排除 111 和 nnn 本身)，再减去在区间 [n/2,n][n / 2, n][n/2,n] 的素数数 pre[n−1]−pre[n/2]pre[n - 1] - pre[n / 2]pre[n−1]−pre[n/2] 即可。 时间复杂度 O(maxn+t)O(maxn + t)O(maxn+t)。 目前提交记录用时最优解