题解 | #many sum#
many sum
https://www.nowcoder.com/practice/e3fea0cb64e24f468e39299a898676fe
题干并不清晰，所以这里重述一下：
给定三个整数 ,
,
，定义两个序列如下：
-
序列
：
-
序列
：
请你计算：
其中 表示按位异或（XOR）。
核心思路
核心观察
1. 
不取模！
题目明确说 “ 输入的东西”，因此：
- 即使
，也不能写成
A[1] = a % m - 只有
时才应用
% M
⚠️ 这是本题最大陷阱！
2. 
是“约数和”，不是“异或和”
（
）加起来
- 最后才对所有的
- 不能跳过
3. 高效计算 ：倍数筛法
直接对每个 枚举约数需
，太慢。
改用反向思维：
- 对每个
到
，
- 将
的倍数位置：
时间复杂度：，可处理
。
算法步骤
- 读入
- 生成序列
（原值）
- 对
到
- 初始化
- 倍数筛法求
复杂度分析
-
时间复杂度：
- 生成序列
，
- 倍数筛法计算
，
- 最终异或答案需
- 整体主导项为
。
- 生成序列
-
空间复杂度：
- 存储序列
- 存储序列
代码
#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;
}
查看8道真题和解析
