洛谷P5495 【模板】Dirichlet 前缀和 题解

题目链接：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;
}