题解：子集和模 m 计数问题

问题分析

我们面对一个两层结构的问题：

第一层（数论化简）：计算 $F(m, a, b) = \gcd(m^a - 1, m^b - 1) + 1$ 然后令 $L = F(m, a, b) + 1, \quad R = F(m, c, d)$ 得到连续整数集合 $S = \{L, L+1, \dots, R\}$。

第二层（组合计数）：统计 $S$ 的子集中，元素和模 $m$ 余 $0$ 的子集个数。

---

第一部分：数论化简

关键引理

对于整数 $x > 1$ 和正整数 $a, b$： $\gcd(x^a - 1, x^b - 1) = x^{\gcd(a, b)} - 1$

证明思路：

1. 设 $d = \gcd(a, b)$，则 $x^d - 1$ 整除 $x^a - 1$ 和 $x^b - 1$
2. 利用辗转相除思想：$\gcd(x^a-1, x^b-1) = x^{\gcd(a,b)}-1$

特殊情况处理

题目说明：若 $a=0$ 或 $b=0$，则 $F(m, a, b)=0$。
因为 $m^0 - 1 = 0$，而 $\gcd(0, x) = |x|$，但特别约定为 $0$。

化简结果

根据引理： $ F(m, a, b) = \gcd(m^a-1, m^b-1) + 1 = (m^{\gcd(a, b)} - 1) + 1 = m^{\gcd(a, b)} $ 当 $a=0$ 或 $b=0$ 时，$\gcd(a,b)$ 可能为另一个数，但 $F$ 被定义为 $0$。

严格来说：

• 若 $a>0$ 且 $b>0$：$F(m, a, b) = m^{\gcd(a, b)}$
• 若 $a=0$ 或 $b=0$：$F(m, a, b) = 0$

因此： $ L = F(m, a, b) + 1 = m^{\gcd(a, b)} + 1 \quad (\text{若 } a,b>0) $ $ R = F(m, c, d) = m^{\gcd(c, d)} \quad (\text{若 } c,d>0) $

重要观察：$L$ 和 $R$ 都是 $m$ 的幂次形式加减常数，$L$ 比某个 $m$ 的幂大 $1$，$R$ 就是某个 $m$ 的幂。

---

第二部分：组合计数

问题重述

给定 $S = \{L, L+1, \dots, R\}$，设 $n = R-L+1$，求 $S$ 的子集中，元素和模 $m$ 余 $0$ 的个数。

关键性质

注意到 $L$ 和 $R$ 都与 $m$ 的幂相关，这暗示集合 $S$ 可能具有模 $m$ 的周期性。

设 $L = m^k + 1$，$R = m^t$（其中 $k, t$ 为 $\gcd(a,b)$ 和 $\gcd(c,d)$）。

由于 $m^k$ 和 $m^t$ 都是 $m$ 的倍数（当 $k,t \ge 1$），所以 $L \equiv 1 \pmod m$，$R \equiv 0 \pmod m$。

那么 $S$ 模 $m$ 的余数序列为： $1, 2, \dots, m-1, 0, 1, 2, \dots, m-1, 0, \dots$ 一个完整的周期长度为 $m$。

计数工具：生成函数与单位根反演

设集合 $S$ 有 $n$ 个元素。每个元素选或不选，生成函数为： $G(x) = \prod_{i \in S} (1 + x^i)$ 我们需要 $G(x)$ 中指数模 $m$ 余 $0$ 的项系数之和。

利用单位根反演公式： $ \text{答案} = \frac{1}{m} \sum_{j=0}^{m-1} G(\omega_m^j) $ 其中 $\omega_m = e^{2\pi i / m}$。

对于每个 $j$，计算： $ G(\omega_m^j) = \prod_{i=L}^{R} (1 + \omega_m^{j i}) $

---

简化乘积计算

设 $S$ 模 $m$ 的余数分布：由于 $S$ 是连续整数区间，每个余数 $0,1,\dots,m-1$ 出现的次数几乎相等。

更精确地：令 $n = R-L+1$，则：

• 完整周期数：$q = \lfloor n/m \rfloor$
• 剩余部分长度：$r = n \bmod m$

对于余数 $k$，出现次数为 $q + [k < r]$（如果从余数 $1$ 开始，需调整偏移）。

但 $L \equiv 1 \pmod m$，所以余数序列确实从 $1$ 开始循环。

因此： $ G(\omega_m^j) = \prod_{k=0}^{m-1} (1 + \omega_m^{j k})^{c_k} $ 其中 $c_k$ 是余数 $k$ 在 $S$ 中出现的次数。

---

特殊情况的封闭形式

当 $j=0$ 时，$\omega_m^0=1$，则： $G(1) = \prod_{i=L}^{R} 2 = 2^n$

当 $j \neq 0$ 时，需要计算： $\prod_{k=0}^{m-1} (1 + \omega_m^{j k})^{c_k}$

由于 $\omega_m^{jk}$ 当 $j$ 与 $m$ 互素时会遍历所有 $m$ 次单位根。若 $\gcd(j, m)=d$，则 $\omega_m^j$ 是 $m/d$ 次本原单位根。

但更关键的是：连续整数模 $m$ 的分布是均匀的（除了边界），且 $n$ 很大时，$c_k$ 几乎相等。

---

利用对称性进一步简化

注意到： $ 1 + \omega_m^{jk} = \omega_m^{jk/2} (\omega_m^{-jk/2} + \omega_m^{jk/2}) = 2\omega_m^{jk/2} \cos\left(\frac{\pi j k}{m}\right) $ 但复数处理麻烦。

更聪明的方法：当 $j \neq 0$ 且 $m$ 为奇数时，$\prod_{k=0}^{m-1} (1+\omega_m^{jk}) = 2$（利用恒等式 $\prod_{k=0}^{m-1} (x-\omega_m^k) = x^m-1$ 代入 $x=-1$）。

因此，如果每个余数出现次数相同（即 $m \mid n$），则： $ G(\omega_m^j) = 2^{n/m} \quad (\text{当 } j \neq 0) $ 但这里 $c_k$ 可能差 $1$，需要微调。

---

第三部分：算法框架

步骤1：计算 $L$ 和 $R$

• 计算 $g_1 = \gcd(a, b)$，$g_2 = \gcd(c, d)$
• 注意 $a,b,c,d$ 可能为 $0$ 的特判
• $L = m^{g_1} + 1$（若 $a,b>0$，否则按定义）
• $R = m^{g_2}$（若 $c,d>0$，否则按定义）

步骤2：确定 $n = R-L+1$ 和模 $m$ 分布

• 计算 $q = \lfloor n/m \rfloor$，$r = n \bmod m$
• 余数 $k$ 出现次数：$c_k = q + \mathbf{1}[k < r]$（考虑 $L \bmod m$ 的偏移调整）

步骤3：应用单位根反演

$ \text{答案} = \frac{1}{m} \sum_{j=0}^{m-1} \prod_{k=0}^{m-1} (1 + \omega_m^{jk})^{c_k} $

由于 $m \le 10^7$，直接枚举 $j$ 并计算乘积可能太慢。

步骤4：高效计算

观察到：

• 对于 $j=0$：贡献为 $2^n$
• 对于 $j \neq 0$：$(1+\omega_m^{jk})^{c_k}$ 可以快速幂计算，但需在模 $998244353$ 下进行，需要找到 $m$ 次本原根模 $998244353$。

更好的方法是利用**离散傅里叶变换(DFT)**的思想： $ \text{答案} = \frac{1}{m} \sum_{j=0}^{m-1} \prod_{k=0}^{m-1} (1 + \omega_m^{jk})^{c_k} $ 交换乘积和求和顺序困难，但注意 $c_k$ 只有两种值：$q$ 或 $q+1$。

设 $A = \prod_{k=0}^{m-1} (1 + \omega_m^{jk})^q$，则： $ \prod_{k=0}^{m-1} (1 + \omega_m^{jk})^{c_k} = A \cdot \prod_{k=0}^{r-1} (1 + \omega_m^{jk}) $ 而 $A = [\prod_{k=0}^{m-1} (1 + \omega_m^{jk})]^q$。

已知 $\prod_{k=0}^{m-1} (1 + \omega_m^{jk}) = 2$ 当 $j$ 与 $m$ 互素？需要验证：代入 $x=-1$ 到 $x^m-1=\prod_{k=0}^{m-1}(x-\omega_m^k)$： $ (-1)^m - 1 = \prod_{k=0}^{m-1} (-1 - \omega_m^k) = (-1)^m \prod_{k=0}^{m-1} (1 + \omega_m^k) $ 所以： $\prod_{k=0}^{m-1} (1 + \omega_m^k) = 1 - (-1)^m$ 即：

• 若 $m$ 为奇数，值为 $2$
• 若 $m$ 为偶数，值为 $0$

但这是 $j=1$ 的情况。对于 $j$ 与 $m$ 互素，乘积相同；对于 $\gcd(j,m)=d>1$，$\omega_m^j$ 是 $m/d$ 次本原单位根，乘积需重新计算。

---

第四部分：实际实现考虑

由于 $m \le 10^7$，不能直接枚举 $j$ 计算。需要利用：

1. 对称性：$G(\omega_m^j)$ 只依赖于 $\gcd(j, m)$
2. 分组计算：将 $j$ 按 $\gcd(j,m)$ 分组，每组大小 $\varphi(m/d)$
3. 预计算：对每个 $d \mid m$，计算 $\prod_{k=0}^{m-1} (1 + \omega_m^{d k})^{c_k}$ 模 $998244353$

但 $m$ 可达 $10^7$，因子个数不多（最多几百），所以可行。

最终算法：

• 枚举 $m$ 的因子 $d$
• 计算 $g_d = \prod_{k=0}^{m-1} (1 + \omega_m^{d k})^{c_k}$ 在模意义下的值
• 答案 = $\frac{1}{m} \sum_{d|m} \varphi(m/d) \cdot g_d$

这样复杂度为 $O(\sigma(m) \cdot m)$，$\sigma(m)$ 是因子个数，在 $10^7$ 内可接受。

---

总结

本题是数论与组合的深度结合：

1. 用 $\gcd$ 公式化简 $F$ 函数，得到 $L,R$ 的简洁形式
2. 将子集和模计数转化为单位根反演问题
3. 利用数论对称性（因子分组）降低计算复杂度
4. 在模质数下用原根代替复数单位根进行计算

关键突破点在于认识到 $L,R$ 的特殊形式导致余数分布均匀，以及利用 $\gcd$ 分组加速单位根反演的计算。