[C++知识库]【luogu P5495】Dirichlet 前缀和

链接

luogu P5495

题目描述

给出数列a，求数列b的和，bi的值=a[所有i的约数]的和

思路

求出质数数列p，显然有$$a_i=\sum a_{i/p}$$
因为有$$b_i=\sum a_{i/d}$$
而$d$可以通过质因数分解
一层层向上递增就好了
其实就是一个前缀和

代码

#include<algorithm> 
#include<iostream>
#include<cstring>
#include<cstdio>
#define uint unsigned int

using namespace std;

uint n, q, k, ans, t;
bool b[20000005];
int p[20000005];
uint a[20000005];
uint seed;

inline uint getnext(){
	seed ^= seed<<13;
	seed ^= seed>>17;
	seed ^= seed<<5;
	return seed;
}//题目所需要的随机求a数列

uint read() 
{
	int x = 0, flag = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') flag = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
	return x * flag;
}

void write(uint x)
{
    if (x < 0) { 
		x = -x; 
		putchar('-');
	}
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
	return;
}

int main()
{
	scanf("%llu%llu", &n, &seed);
	for(int i = 2; i <= n; ++i)
	{
		if(!b[i]) {
			b[i] = 1;
			p[++t] = i;
		} 
		for(int j = 1; j <= t && i * p[j] <= n; ++j)
			b[i * p[j]] = 1;
	}
	for(int i = 1; i <= n; ++i)
		a[i] = getnext();
	for(int i = 1; i <= t; ++i)
	for(int j = 1; p[i] * j <= n; ++j)
		a[p[i] * j] += a[j];
	ans = a[1];
	for(int i = 2; i <= n; ++i)
		ans ^= a[i];
	printf("%llu", ans);
	return 0;
}