洛谷P5495 【模板】Dirichlet 前缀和 题解
题意：
给定一个长度为 \(n\) 的数列 \(a_1,a_2,a_3,\dots,a_n\)。
现在你要求出一个长度为 \(n\) 的数列 \(b_1,b_2,b_3,\dots,b_n\)，满足
\[ b_k=\sum_{i\mid k}a_i \] 由于某些神秘原因，这里的 \(b_k\) 要对 \(2^{32}\) 取模。
输入格式：
为了避免过大的输入，本题的输入使用随机数生成器。
输入中只有一行两个整数 \(n,\mathrm{seed}\)。其中 \(\mathrm{seed}\) 为 \(32\) 位无符号整数，用来生成数据。
接下来，你要调用 \(n\) 次随机数生成器，分别生成 \(a_1\sim a_n\)。随机生成器见原题链接。
输出格式：
为了避免过大的输出，你只需输出一个 \(32\) 位无符号整数，表示所有 \(b_i\) 的异或和。
数据范围：
\(1\leq n\leq 2\times 10^7\)，\(0\leq \mathrm{seed}< 2^{32}\)。
设 \(i = \prod p_k^{\alpha_k},~j = \prod p_k^{\beta_k}\) ，其中 \(p\) 均为素数。
那么 \(a_i\) 对 \(b_j\) 有贡献当且仅当 \(\forall k,~\alpha_k \le \beta_k\) 。
可以发现这是一个高维前缀和，即如果我们给每个 \(p\) 都开一维的话，答案可以这么算 \[ f(x_1,x_2,\cdots,x_k) = f(x_1-1,x_2,\cdots,x_k) + f(x_1,x_2-1,\cdots,x_k)+\cdots + f(x_1,x_2,\cdots,x_k-1) - \cdots \] 这里没写全，后面的省略号表示容斥要减去的东西，这个应该很好理解。
不过这意思有些过于蠢了。我们已经知道 \(\prod p_i^{x_i}\) 了，完全可以记一个 \(f_i\) ，每次从质因子处得到贡献。
直接枚举质因子还是很蠢，我们可以用埃氏筛。
这样时间复杂度就是 \(\mathcal{O}(n \log \log n)\) ，埃氏筛的复杂度证明参考 link
代码：
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define uint unsigned int
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e7 + 15))
uint _, res, f[N], a[N]; char chk[N];
uint rd() { _ ^= _ << 13; _ ^= _ >> 17; _ ^= _ << 5; return _; }
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n; cin >> n >> _;
rep(i, 1, n) f[i] = a[i] = rd();
chk[1] = 1;
rep(i, 1, n)
{
if(!chk[i]) rep(j, 1, n / i) {
f[i * j] += f[j], chk[i * j] = true;
} res ^= f[i];
}
cout << res << '\n';
return 0;
}
