题解 | #many sum#_牛客博客

1. 问题分析

本题的核心要求是处理两个具有依赖关系的序列 $A$ 和 $B$ 。

序列 A：基于线性同余的递推关系， $A_i$ 仅依赖于 $A_{i-1}$ 。这是一个单调生成的序列。
序列 B： $B_i$ 定义为 $i$ 的所有约数 $d$ 对应的 $A_d$ 之和。这是一个经典的数论变换问题（Dirichlet Convolution 的变种，即 $B = A * 1$ ，其中 $1$ 是全 1 序列）。
目标：计算整个序列 $B$ 的异或和。

不可行的思路：

naive 算法的不可行性：最直观的做法是，先生成 $A$ ，然后对每个 $i$ 枚举其约数计算 $B_i$ 。对于每个数 $i$ ，枚举约数的时间复杂度为 $O(\sqrt{i})$ 。总复杂度为 $\sum_{i=1}^N \sqrt{i} \approx O(N\sqrt{N})$ 。当 $N=2 \times 10^6$ 时，计算量达到 $10^9$ 级别，显然超时。
$A$ 的非积性：序列 $A$ 的生成公式 $A_i = (A_{i-1} + 7i) \pmod M$ 本质上是一个二次函数（求和公式导致）。 $A$ 并不具备积性函数（Multiplicative Function）的性质（即 $A_{nm} \neq A_n A_m$ ），这意味着我们无法直接使用欧拉筛（Linear Sieve）在 $O(N)$ 时间内通过积性推导 $B$ 。

2. 核心算法：调和级数筛法 (贡献法)

为了优化计算 $B_i$ 的过程，我们需要转换视角通过贡献法来改变计算顺序。

原始视角：对于每个 $i$ ，去寻找它的因子 $d$ 。即 "谁是我的因子？"
优化视角：对于每个 $d$ ，去寻找它的倍数 $i$ 。即 "我是谁的因子？"

根据定义 $B_i = \sum_{d|i} A_d$ ，这意味着 $A_d$ 会被累加到 $B_{d}, B_{2d}, B_{3d}, \dots, B_{k \cdot d}$ 中。我们可以遍历 $i$ 从 $1$ 到 $N$ ，将 $A_i$ 的值累加到所有 $i$ 的倍数位置的 $B$ 数组中。

为什么选择此范式： 这种基于倍数的遍历方式（类似埃氏筛法 Eratosthenes Sieve 的逻辑），其复杂度受调和级数控制，远优于 $O(N\sqrt{N})$ ，且无需 $A$ 具备积性函数特征，是解决此类通用约数和问题的最优解。

3. 算法复杂度分析

时间复杂度：序列 $A$ 的生成为 $O(N)$ 。序列 $B$ 的计算涉及两层循环：外层枚举 $i$ 从 1 到 $N$ ，内层枚举倍数 $j = i, 2i, \dots$ 。总操作次数为： $\frac{N}{1} + \frac{N}{2} + \frac{N}{3} + \dots + \frac{N}{N} = N \sum_{i=1}^N \frac{1}{i} \approx N \ln N$ 因此，时间复杂度为 $O(N \log N)$ 。

对比：在 $N=2 \times 10^6$ 下， $N \log N \approx 3 \times 10^7$ 次操作，完全符合 1 秒的时限要求。
空间复杂度：我们需要存储序列 $B$ 来累加结果。空间复杂度为 $O(N)$ 。 优化点：序列 $A$ 不需要完整保存，可以在遍历 $i$ 时动态生成 $A_i$ ，从而将辅助空间减少一半。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, A1, M;
    cin >> N >> A1 >> M;

    vector<int> B(N + 1, 0);
    int curA;
    int lastA;

    for (int i = 1; i <= N; i++) {
        curA = (i == 1) ? A1 : (lastA + 7 * i) % M;
        lastA = curA;
        for (int j = i; j <= N; j += i) {
            B[j] += curA;
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans ^= B[i];
    }
    cout << ans << endl;
}