题解：购买方案计数

问题转化

给定 $N, G, L$，要求统计所有非空集合 $S \subseteq \{1,2,\dots,N\}$，满足：

$$\gcd(S) = G,\quad \mathrm{lcm}(S) = L$$

对于每个询问 $X$，求有多少个这样的集合 $S$ 包含 $X$。

答案对 $10^9+7$ 取模。

关键推导

1. 基本转化

若 $G \nmid L$ 则无解，答案为 $0$。 令 $L' = L/G$，则问题转化为：选择若干个数 $a_i$，使得：

• $a_i$ 是 $G$ 的倍数，即 $a_i = G \cdot b_i$
• $\gcd\{b_i\} = 1$
• $\mathrm{lcm}\{b_i\} = L'$
• $b_i \le N/G$

即转化为 $G=1$ 的情况：在 $[1, N']$ 中选择若干数，$\gcd=1$，$\mathrm{lcm}=L'$。

2. 因子分解

设 $L' = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$，其中 $p_i$ 是质数。

对每个质因子 $p_j$，选择的数集合 $S$ 中：

• 至少有一个数的 $p_j$ 指数为 $0$（保证 $\gcd=1$）
• 至少有一个数的 $p_j$ 指数为 $e_j$（保证 $\mathrm{lcm}=L'$）
• 每个数的 $p_j$ 指数在 $[0, e_j]$ 之间

3. 独立计数

对于每个质因子 $p_j$，选择的数在 $p_j$ 上的指数情况是独立的。 记 $m_j = e_j$，对于每个数，它在 $p_j$ 上的指数可以是 $0,1,\dots,m_j$，但必须满足上述条件。

设对于质因子 $p_j$，有 $c_j$ 个数指数为 $0$，$d_j$ 个数指数为 $m_j$，且 $c_j \ge 1$，$d_j \ge 1$。

4. 总方案数

先不考虑是否包含 $X$，计算总合法集合数。

设 $M = N' = N/G$，需要 $b_i \le M$ 且包含所有 $L'$ 的质因子条件。

实际可选的数集合是 $L'$ 的约数集合中不超过 $M$ 的部分。

令 $U = \{ d \mid d \text{ 是 } L' \text{ 的约数}, d \le M \}$。

我们需要 $S \subseteq U$，$S \neq \varnothing$，且满足对每个质因子 $p_j$：

• $\min_{x \in S} v_{p_j}(x) = 0$
• $\max_{x \in S} v_{p_j}(x) = m_j$

5. 容斥计算

记 $f(S)$ 为满足条件的集合数。

用容斥：

• 去掉“至少一个质因子不满足 $\min=0$”的条件
• 去掉“至少一个质因子不满足 $\max=m_j$”的条件

设 $A_j$ 表示“所有数的 $p_j$ 指数都 $\ge 1$”（即 $\min \ge 1$）
设 $B_j$ 表示“所有数的 $p_j$ 指数都 $\le m_j-1$”（即 $\max \le m_j-1$）

则合法集合 = 总非空集合 - 存在 $j$ 满足 $A_j$ - 存在 $j$ 满足 $B_j$ + 存在 $j_1,j_2$ 满足 $A_{j_1}$ 和 $B_{j_2}$ 的交集 + ……

6. 约数筛选

对于每个子集 $T \subseteq \{1,\dots,k\}$，定义：

• $C_T$：所有数的 $p_j$ 指数 $\ge 1$（对 $j \in T$）的限制下，可选的数的个数
• $D_T$：所有数的 $p_j$ 指数 $\le m_j-1$（对 $j \in T$）的限制下，可选的数的个数

实际 $C_T$ 对应 $L'$ 的约数中，被 $\prod_{j\in T} p_j$ 整除且 $\le M$ 的个数。
$D_T$ 对应 $L'$ 的约数中，不被 $p_j^{m_j}$ 整除（对 $j\in T$）且 $\le M$ 的个数。

7. 总方案公式

记 $F(T_1, T_2)$ 为满足“对 $j\in T_1$，指数 $\ge 1$；对 $j\in T_2$，指数 $\le m_j-1$”的数的个数。

则合法集合数：

$$\sum_{T_1 \subseteq [k]} \sum_{T_2 \subseteq [k]} (-1)^{|T_1|+|T_2|} \left(2^{F(T_1,T_2)} - 1\right) $$

其中 $[k]=\{1,\dots,k\}$，且 $T_1,T_2$ 可能相交。

8. 包含 $X$ 的方案数

设 $X' = X/G$，需要 $X'$ 是整数且 $X' \mid L'$，否则答案为 $0$。

对每个询问 $X$，需要计算包含 $X'$ 的合法集合数。

固定 $X'$，对于其他数的选择，必须满足：

• 集合整体 $\gcd=1$，$\mathrm{lcm}=L'$
• 包含 $X'$

设 $X'$ 的质因数指数为 $r_j$（$0 \le r_j \le m_j$）。

则条件变为：

• 对每个 $j$：$\min(r_j, \text{其他数指数}) = 0$
• 对每个 $j$：$\max(r_j, \text{其他数指数}) = m_j$

即：

• 若 $r_j = 0$，则其他数中必须有指数 $0$（已满足），且必须有指数 $m_j$
• 若 $r_j = m_j$，则其他数中必须有指数 $0$，且必须有指数 $m_j$（已满足）
• 若 $0 < r_j < m_j$，则其他数中必须有指数 $0$ 和 $m_j$

9. 计算包含 $X'$ 的方案数

令 $S_0 = \{j \mid r_j = 0\}$
$S_m = \{j \mid r_j = m_j\}$
$S_mid = \{j \mid 0 < r_j < m_j\}$

对于其他数 $y$，必须满足：

• 对 $j \in S_0$：$v_j(y) \ge 0$（无限制），但必须有某个 $y$ 满足 $v_j(y)=m_j$
• 对 $j \in S_m$：$v_j(y) \le m_j$（无限制），但必须有某个 $y$ 满足 $v_j(y)=0$
• 对 $j \in S_mid$：$v_j(y)$ 任意，但必须有某个 $y$ 满足 $v_j(y)=0$，且某个 $y$ 满足 $v_j(y)=m_j$

用容斥计算不含 $X'$ 的其他数的选择方案数，再乘 $1$（固定 $X'$ 在集合中）。

10. 实现简化

由于 $k \le \omega(L') \le 8$（因为 $L \le 10^8$），可以 $O(3^k)$ 或 $O(4^k)$ 枚举所有质因子条件状态，对每个状态预处理可选的数的个数。

对每个询问 $X$：

• 检查 $G \mid X$ 且 $X' \mid L'$，否则输出 $0$
• 根据 $X'$ 的指数向量，确定 $S_0,S_m,S_mid$
• 用容斥计算其他数的选择方案数

算法步骤

1. 分解 $L' = L/G$ 的质因数 $p_1^{e_1} \cdots p_k^{e_k}$
2. 预处理 $M = N/G$ 以内所有 $L'$ 的约数，对每个约数记录其指数向量
3. 预处理 $cnt[mask]$：指数向量满足某些条件的约数个数（mask 表示每个质因子的指数是否满足某些条件）
4. 对每个询问 $X$：
   • 若 $G \nmid X$ 或 $(X/G) \nmid L'$，输出 $0$
   • 计算 $X' = X/G$ 的指数向量 $r$
   • 确定 $S_0,S_m,S_mid$
   • 用容斥计算其他数的选择方案数 $ways$
   • 输出 $ways$

复杂度

• 预处理：$O(\sigma(L') \cdot k)$，其中 $\sigma(L')$ 是 $L'$ 的约数个数
• 每个询问：$O(3^k)$ 或 $O(2^{2k})$
• 由于 $k \le 8$，可过