题解 | #many sum#

题干并不清晰，所以这里重述一下： 给定三个整数 , , ，定义两个序列如下：

• 序列 ：

  
  

• 序列 ：

  

请你计算：

其中 表示按位异或（XOR）。

核心思路

核心观察

1. 不取模！

题目明确说 “ 输入的东西”，因此：

• 即使 ，也不能写成 A[1] = a % m
• 只有 时才应用 % M

⚠️ 这是本题最大陷阱！

2. 是“约数和”，不是“异或和”

• 是加法求和：把所有 （）加起来
• 最后才对所有的 做异或
• 不能跳过 数组直接异或 （因为异或 ≠ 加法）

3. 高效计算 ：倍数筛法

直接对每个 枚举约数需 ，太慢。
改用反向思维：

• 对每个 到 ，
• 将 加到所有 的倍数位置：

时间复杂度：，可处理 。

算法步骤

1. 读入
2. 生成序列 ：
   • （原值）
   • 对 到 ：
3. 初始化
4. 倍数筛法求 ：

复杂度分析

• 时间复杂度：

  • 生成序列 需 ，
  • 倍数筛法计算 的总操作次数为 ，
  • 最终异或答案需 ，
  • 整体主导项为 。

• 空间复杂度：

  • 存储序列 和 各需 空间。

代码

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

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

    long long n, a, m;
    cin >> n >> a >> m;

    vector<long long> A(n + 1);
    A[1] = a ;
    for (int i = 2; i <= n; i++) {
        A[i] = (A[i - 1] + 7LL * i) % m;
    }

    // 先计算 B[i] = sum_{d|i} A[d]
    vector<long long> B(n + 1, 0);
    for (int d = 1; d <= n; d++) {
        for (int i = d; i <= n; i += d) {
            B[i] += A[d];
        }
    }

    // 再异或所有 B[i]
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans ^= B[i];
    }

    cout << ans << '\n';
    return 0;
}