Dirichlet 前缀和

原题链接：Link

问题简介

已知序列 \(a_n\) ，求出序列 \(b_n\) ，其中：

\[ b_i=\sum_{j|i}{a_j} \]

解决方法

一种显然的写法就是寻找每个 \(i\) 的倍数，让 \(b_i \leftarrow b_i + a_i,b_{2i} \leftarrow b_{2i} + a_i,b_{3i} \leftarrow b_{3i} + a_i\) …… 来算贡献。这样的时间复杂度是 \(N \ln N\) 的。不够优秀。

我们来考虑这样的一个数： \(x=a\cdot p^k\) 。他会受到哪些数的贡献呢？显然，是 \(a \cdot p^0,a \cdot p^1,a \cdot p^2...a \cdot p^k-1,a \cdot p^k\) 。那么我们可以这样：让 \(a \cdot p^0\) 先给 \(a \cdot p^1\) 做贡献，再让 \(a \cdot p^1\) 带着自己和 \(a \cdot p^0\) 的贡献一起给 \(a \cdot p^2\) 做贡献，然后 \(a \cdot p^2\) 再带着 \(a \cdot p^0\) 与 \(a \cdot p^1\) 的贡献一起给 \(a \cdot p^3\) 做贡献……依次类推，以 \(p\) 为步长的贡献就算完了。在 \(O(N)\) 的时间就可以把所有的 \(a\) 的贡献算出来，如下：

1
2
3

for (int i = 1; i <= n; i++) {
	a[p * i] += a[i];
}

结合上面的分析，好好体会一下这三行代码的含义。

但是这只做了 \(p\) 的贡献。我们需要让每个质数都做一次贡献，这样才能不重不漏（因为质因数分解是唯一的）。提前筛出质数，枚举 \(p\) 即可。

1
2
3

for(int i = 1; i <= tot; i++)
	for(int j = 1; pri[i] * j <= n; j++)
		a[pri[i] * j] += a[j];

这个时间复杂度和埃氏筛是一样的， \(O(N \log \log N)\) 。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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

#define uint unsigned int
uint seed;
inline uint getnext(){
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}

const uint maxn = 2e7 + 5;

uint n, ans;
uint a[maxn];
bool np[maxn];
uint pr[maxn], pcnt;

int main() {
	scanf("%u %u", &n, &seed);
	for (uint i = 1; i <= n; i++) {
		a[i] = getnext();
	}
	for (uint i = 2; i <= n; i++) {
		if (!np[i]) pr[++pcnt] = i;
		for (uint j = 1; j <= pcnt && i * pr[j] <= n; j++) {
			np[i * pr[j]] = true;
			if (i % pr[j] == 0) break;
		}
	}
	for (uint i = 1; i <= pcnt; i++) {
		for (uint j = 1; pr[i] * j <= n; j++) {
			a[pr[i] * j] += a[j];
		}
	}
	for (uint i = 1; i <= n; i++) {
		ans ^= a[i];
	}
	printf("%u\n", ans);
	return 0;
}