给定一个长度为 n 的数列 a1,a2,a3,…,an。
现在你要求出一个长度为 n 的数列 b1,b2,b3,…,bn，满足
bk=i∣k∑ai
由于某些神秘原因，这里的 bk 要对 232 取模。
为了避免过大的输入，本题的输入使用随机数生成器。
输入中只有一行两个整数 n,seed。其中 seed 为 32 位无符号整数，用来生成数据。
接下来，你要调用 n 次随机数生成器，分别生成 a1∼an。
对于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 位无符号整数，表示所有 bi 的异或和。
类似于埃氏筛和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
54
| // 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;
}
|
v1.4.14