题目链接：https://www.luogu.com.cn/problem/P5495
模型转化：
题目要求计算 \(b_k = \sum_{i|k} a_i\)。
任何正整数都可以唯一分解为质因子的乘积：\(i = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m}\)。
\(i\) 能够整除 \(k\) 的充要条件是：对于 \(k\) 的每一个质因子 \(p_j\)，其在 \(i\) 中的指数都小于或等于在 \(k\) 中的指数。这本质上是一个以无限个质数为坐标轴的高维前缀和问题。
高维前缀和（SOS DP）：
就像求多维数组前缀和一样，我们不需要使用容斥原理，而是可以逐维累加。
在数论中，每一个质数 \(p\) 就代表其中的一维。因此，我们可以外层循环枚举所有小于等于 \(n\) 的质数 \(p\)，内层循环从小到大枚举倍数，更新 \(a_{j \cdot p} \leftarrow a_{j \cdot p} + a_{j}\)。
示例程序：
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
const int maxn = 2e7 + 5;uint seed;
inline uint getnext(){seed^=seed<<13;seed^=seed>>17;seed^=seed<<5;return seed;
}
int n;uint a[maxn], ans;bool isp[maxn];
int prime[maxn / 10], m;
void init(int n) {for (int i = 2; i <= n; i++) {if (!isp[i]) {prime[++m] = i;for (int j = i; j <= n/i; j++)isp[i * j] = true;}}
}int main() {cin >> n >> seed;for (int i = 1; i <= n; i++)a[i] = getnext();init(n);for (int i = 1; i <= m; i++) {for (int j = 1; prime[i] * j <= n; j++) {a[prime[i] * j] += a[j];}}for (int i = 1; i <= n; i++)ans ^= a[i];cout << ans << endl;return 0;
}