【学习笔记】Dirichlet前缀和

\(\text{Solution:}\)

观察到一个\(a_i\)若对\(a_j\)有贡献，则必须\(i\)的所有质因子幂次小于等于\(j\)的质因子幂次。

于是，我们可以枚举质数的倍数并累加即可。其实就是把直接枚举每个数的倍数改为枚举质数的倍数，可以把\(O(n\log n)\)优化到\(O(n\log \log n).\)

注意：埃氏筛筛积性函数是可以做到\(O(n\log\log n)\)的（枚举质数的倍数），而直接枚举每一个数的倍数应该是\(O(n\log n)\)的。

#include<bits/stdc++.h>

using namespace std;

const int MAXN=20000000;

#define uint unsigned int

uint seed;

inline uint getnext(){

	seed^=seed<<13;

	seed^=seed>>17;

	seed^=seed<<5;

	return seed;

}

bitset<MAXN+1>vis;

int cnt,n;

uint a[MAXN],ans,p[MAXN];

int main(){

	scanf("%d",&n);

	scanf("%u",&seed);

	for(int i=1;i<=n;++i)a[i]=getnext();

	for(int i=2;i<=MAXN;++i){

		if(!vis[i])p[++cnt]=i;

		for(int j=1;j<=cnt&&i*p[j]<=MAXN;++j){

			vis[i*p[j]]=1;

			if(i%p[j]==0)break;

		}

	}

	for(int i=1;i<=cnt;++i){

		for(int j=1;j*p[i]<=MAXN;++j){

			a[j*p[i]]+=a[j];

		}

	}

	for(int i=1;i<=n;++i)ans^=a[i];

	cout<<ans<<endl;

	return 0;

}

巴特西

【学习笔记】Dirichlet前缀和

最新文章

热门文章