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|k}a_i$$
由于某些神秘原因，这里的 $b_k$ 要对 $2^{32}$ 取模。
输入格式:
为了避免过大的输入，本题的输入使用随机数生成器。
输入中只有一行两个整数 $n,seed$。其中 $seed$ 为 $32$ 位无符号整数，用来生成数据。
接下来，你要调用 $n$ 次随机数生成器，分别生成 $a_1\sim a_n$。
对于C/C++选手，生成器模板如下：
1
2
3
4
5
6
7
8
| #define uint unsigned int
uint seed;
inline uint getnext(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
|
对于Pascal选手，生成器模板如下：
1
2
3
4
5
6
7
8
| var seed:dword;
function getnext:dword;
begin
seed:=seed xor(seed shl 13);
seed:=seed xor(seed shr 17);
seed:=seed xor(seed shl 5);
getnext:=seed;
end;
|
注意：所有 $n$ 个数均为 $32$ 位无符号整数。
输出格式:
为了避免过大的输出，你只需输出一个 $32$ 位无符号整数，表示所有 $b_i$ 的异或和。
样例:
样例输入1:
样例输出1:
思路:
类似于埃氏筛和FMT
实现:
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
43
44
45
46
47
48
49
50
51
52
53
| // Problem: P5495 Dirichlet 前缀和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5495
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
#define uint unsigned int
uint seed;
inline uint getnext()
{
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
return seed;
}
uint t[30000000], pri[3000000], cnt, ans;
bool prim[30000000];
int main()
{
uint n;
yin >> n >> seed;
for (uint i = 2; i <= n; i++)
if (!prim[i])
for (uint j = 2 * i; j <= n; j += i)
prim[j] = 1;
for (uint i = 2; i <= n; i++)
if (!prim[i])
pri[++cnt] = i;
for (uint i = 1; i <= n; i++)
t[i] = getnext();
for (uint i = 1; i <= cnt; i++)
{
for (uint j = 1; pri[i] * j <= n; j++)
{
t[j * pri[i]] += t[j];
}
}
for (uint i = 1; i <= n; i++)
{
ans ^= t[i];
}
yout << ans;
}
|