题解：倍数计数与前缀和优化算法

---

问题分析

本题模拟了一个循环操作：对于每个跳跃步长 $X_i$，将所有下标为 $X_i$ 倍数的位置加1。执行 $K$ 次后，需要回答 $Q$ 个区间和查询。

朴素做法：直接模拟每次操作需要 $O(K \cdot \frac{N}{X_i})$，最坏 $O(KN)$，不可行。需要优化。

---

关键观察

1. 问题本质

对于位置 $j$（$0 \le j < N$），它的值 $\text{seq}[j]$ 等于满足 $j$ 是 $X_i$ 倍数的 $i$ 的个数。

即：

$$\text{seq}[j] = \#\{i \mid X_i \text{ 整除 } j\}$$

其中 $X_i$ 整除 $j$ 表示 $j$ 是 $X_i$ 的倍数（注意 $j=0$ 时，所有 $X_i$ 都整除它）。

2. 转化为倍数计数

设 $cnt[d]$ 表示步长 $d$ 出现的次数。那么：

$$\text{seq}[j] = \sum_{d \mid j} cnt[d]$$

其中 $d \mid j$ 表示 $d$ 整除 $j$（$j$ 是 $d$ 的倍数）。

3. 高效计算

需要对于所有 $j=0,\dots,N-1$ 计算其所有因子的 $cnt$ 之和。可以使用倍数枚举法（类似埃氏筛）在 $O(N \log N)$ 时间内完成。

---

算法框架

第一步：统计步长频率

for (int i = 1; i <= k; ++i) {
    int x;
    scanf("%d", &x);
    ++cnt[x];  // cnt[d]记录步长d出现的次数
}

第二步：倍数枚举计算seq值

关键代码：

for (int i = n>>1; i; --i)
    for (int j = i*2; j < n; j += i)
        seq[j] += cnt[i];

解释：

• 从 $N/2$ 向下枚举到1
• 对于每个 $i$，枚举 $i$ 的所有倍数 $j = 2i, 3i, \dots < N$
• 将 $cnt[i]$ 加到 $seq[j]$ 上

这样，最终 $seq[j]$ 就包含了所有满足 $i \mid j$ 的 $cnt[i]$ 之和。

第三步：处理特殊情况 $j=0$

$j=0$ 是所有 $X_i$ 的倍数（因为 $0$ 除以任何非零数都得0）：

seq[0] = k;  // 所有K次操作都会访问位置0

第四步：前缀和优化查询

预处理前缀和：

for (int i = 1; i < n; ++i)
    prefix[i] = prefix[i-1] + seq[i];

查询 $[L,R]$ 区间和：

printf("%lld\n", prefix[R] - (L ? prefix[L-1] : 0));

---

复杂度分析

• 时间复杂度：

  • 倍数枚举：$O(\sum_{i=1}^{N} \frac{N}{i}) = O(N \log N)$
  • 前缀和预处理：$O(N)$
  • 查询：$O(1)$ 每个，总 $O(Q)$
  • 总复杂度：$O(N \log N + Q)$

• 空间复杂度：$O(N)$ 存储 $seq$ 数组

对于 $N \le 10^6$，$N \log N \approx 2 \times 10^7$ 操作，完全可行。

---

正确性证明

1. 倍数枚举的正确性

对于任意 $j > 0$，它的因子 $i$ 必须满足 $i \le j/2$（除了 $j$ 本身，但 $j < N$ 且 $X_i < N$，所以 $j$ 本身不可能是步长）。枚举从 $N/2$ 向下到1，确保所有可能的因子都被考虑。

更严谨的证明：对于每个 $j$，$seq[j] = \sum_{i \mid j, i < N} cnt[i]$。由于 $i > j/2$ 且 $i \mid j$ 时 $i$ 只能是 $j$ 本身，而 $j < N$ 不在步长范围内，所以只需考虑 $i \le j/2$。

2. 边界处理

• $j=0$：特殊处理，所有操作都访问位置0
• $j>0$：通过倍数枚举计算所有因子的贡献

3. 前缀和优化

区间和查询转化为两个前缀和的差，是标准优化方法。

---

算法优化细节

为什么从 $N/2$ 开始枚举？

因为任何 $j$ 的因子 $i$ 如果满足 $i > j/2$ 且 $i \mid j$，那么 $i$ 只能是 $j$ 本身。而题目保证 $X_i < N$，所以当 $j < N$ 时，$j$ 本身不可能是步长（除非 $j$ 恰好等于某个 $X_i$，但这种情况已由 $cnt[j]$ 直接处理）。

实际上，代码中 j = i*2 开始枚举，确保了 $i$ 严格小于 $j$。

内存优化

直接使用 a[] 数组既存储 $cnt$，又存储 $seq$，最后存储前缀和，节省空间。

---

总结

本题是一道数论与算法优化的综合题目，主要考察：

1. 问题转化能力：将循环操作转化为倍数计数问题
2. 倍数枚举技巧：使用类似埃氏筛的方法高效计算因子和
3. 前缀和优化：将区间查询优化为 $O(1)$ 时间
4. 边界条件处理：正确处理 $j=0$ 的特殊情况

算法的核心技巧：

• 利用 $seq[j] = \sum_{d \mid j} cnt[d]$ 的性质
• 通过从大到小枚举因子，避免重复计算
• 使用前缀和快速回答区间查询

这种"倍数枚举+前缀和"的方法是解决此类"倍数操作+区间查询"问题的经典范式，时间复杂度从朴素的 $O(KN)$ 优化到 $O(N \log N + Q)$。