LGP5495 Dirichlet 前缀和

不是很明白为什么要叫做模板

考虑到\(a_i\)能对\(b_j\)产生贡献，当且仅当\(a_i=\prod p_k^{a_k},b_j=\prod p_k^{b_k},\forall k \ a_k\leq b_k\)，于是我们把每一个质数次幂看成一维，相当于对\(a\)数组求一个高维前缀和

于是我们枚举每一个质数次幂，利用高维前缀和的方式来做就行了，复杂度同埃筛\(\operatorname{O(n\ log\ log\ n)}\)

#include<bits/stdc++.h>

#define re register

#define uint unsigned int

const int maxn=2e7+5;

uint seed,a[maxn],ans;

int n,f[maxn],p[maxn>>2];

inline uint getnxt(){

	seed^=seed<<13;seed^=seed>>17;

	seed^=seed<<5;return seed;

}

int main() {

	scanf("%d%u",&n,&seed);

	for(re int i=2;i<=n;i++) {

		if(!f[i]) p[++p[0]]=i;

		for(re int j=1;j<=p[0]&&p[j]*i<=n;j++) {

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

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

		}

	}

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

	for(re int i=1;i<=p[0];i++)

		for(re int j=2;j*p[i]<=n;j++)

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

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

	printf("%u",ans^a[1]);

	return 0;

}

巴特西

LGP5495 Dirichlet 前缀和

最新文章

热门文章