P5495 Dirichlet 前缀和素数筛 + 高维前缀和

题目背景

模板题，无背景。

题目描述

给定一个长度为 $n$ 的数列 $a1,a2,a3,…,an$ 。
现在你要求出一个长度为 $n$ 的数列 $b1,b2,b3,…,bn$ ，满足

b_k=\sum_{i|k}a_i

由于某些神秘原因，这里的 $b_k$ 要对 $2^{32}$ 取模。

输入格式

为了避免过大的输入，本题的输入使用随机数生成器。
输入中只有一行两个整数 $n,seed$ 。其中 $seed$ 为 $32$ 位无符号整数，用来生成数据。
接下来，你要调用 $n$ 次随机数生成器，分别生成 $a1$ ～ $an$ 。
对于C/C++选手，生成器模板如下：

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

对于Pascal选手，生成器模板如下：

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$ 的异或和。
输入输出样例

样例输入

5 1477

样例输出

2608816472

说明/提示

样例中，数列 $a$ 为 $397153977,974453892,352446086,334987182,2086335567397153977, 974453892, 352446086, \\334987182, 2086335567397153977,974453892,352446086,334987182,2086335567$ 。
数列 $b$ 为 $397153977,1371607869,749600063,1706595051,2483489544397153977, 1371607869, 749600063, \\1706595051, 2483489544397153977,1371607869,749600063,1706595051,2483489544$ 。

限制与约定

对于 $100\%$ 的数据， $1≤n≤2×10^7，0≤seed<2^{32}$ 。

题解

素数筛 + 高维前缀和
先线性筛筛出所有素数，再利用高维前缀和的思想，将每个素数当做一维，分开考虑即可。
时间复杂度： $O(nloglogn)$

code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
const int N = 2e7 + 5;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch^48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
int n, cnt, pri[N], vis[N];
uint ans, seed, a[N];
uint getnext() {seed^=seed<<13; seed^=seed>>17; seed^=seed<<5; return seed;}
void init() {
	for(int i = 1; i <= n; ++ i) a[i] = getnext();
	for(int i = 2; i <= n; ++ i) {
		if(! vis[i]) pri[++ cnt] = i;
		for(int j = 1; j <= cnt && i * pri[j] <= n; ++ j) {
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
}
int main() {
	n = read(); seed = read(); init();
	for(int i = 1; i <= cnt; ++ i) {
		for(int j = 1; j * pri[i] <= n; ++ j) a[j * pri[i]] += a[j];
	}
	for(int i = 1; i <= n; ++ i) ans ^= a[i];
	cout << ans << endl;
	return 0;
}
<!-- more -->