P5495 [Template] Dirichlet Prefix Sum

This is a template problem, with no background.

Given a sequence $a_1,a_2,a_3,\dots,a_n$ of length $n$. Now you need to compute a sequence $b_1,b_2,b_3,\dots,b_n$ of length $n$, satisfying $$b_k=\sum_{i|k}a_i$$ Due to some mysterious reasons, each $b_k$ should be taken modulo $2^{32}$.

To avoid overly large input, this problem uses a random number generator. The input contains only one line with two integers $n, seed$. Here, $seed$ is a $32$-bit unsigned integer used to generate the data. Next, you need to call the random number generator $n$ times to generate $a_1 \sim a_n$. For ```C/C++``` users, the generator template is as follows: ```cpp #define uint unsigned int uint seed; inline uint getnext(){ seed^=seed17; seed^=seed

To avoid overly large output, you only need to output one $32$-bit unsigned integer, which is the XOR sum of all $b_i$.

In the sample, the sequence $a$ is $397153977, 974453892, 352446086, 334987182, 2086335567$. The sequence $b$ is $397153977, 1371607869, 749600063, 1706595051, 2483489544$. ### Constraints and Conventions For $100\%$ of the testdata, $1\leq n\leq 2\times 10^7$, $0\leq seed< 2^{32}$. Translated by ChatGPT 5