Dirichlet 前缀和学习笔记

传送门

求\(b_k=\sum\limits_{i|k}{a_i}\)

考虑\(i=p_1^k,j=p_1^{k+1}\)，若我们已经求出了\(b_i\)，则易知\(b_j=b_i+a_j\)

然后根据上面的方法，考虑对于所有的\(k=p_1^{k1}p_2^{k2}...p_l^{kl}\)，若\(j=p_2^{k2}...p_l^{kl}\)，我们已经求出所有的\(c_k=a_j+a_{p1\times j}+a_{p1^2\times j}+...+a_{p1^{k1}\times j}\)

则对于\(i=p_1^{k1},j=p_1^{k1}p_2\)，若我们求出了\(c_i,c_j\)，则\(b_j=c_i+c_j\)

进一步的，对于\(i=p_1^{k1}p_2,j=p_1^{k1}p_2^2\)，若我们求出了\(b_i\)，则\(b_j=b_i+c_j\)

再进一步，对于\(i=p_1^{k1}p_2^{k2},j=p_1^{k1}p_2^{k2+1}\)，若我们求出了\(b_i\)，则\(b_j=b_i+c_j=\sum\limits_{t=0}^{k2+1}c_{p_1^{k1}p_2^t}\)

我们发现，若我们重复上述步骤，则对于任意数\(k=p_1^{k1}p_2^{k2}...p_l^{kl}\)，我们都可以求出\(b_k\)

那么如何快速求出\(c_i\)呢？

我们可以先令\(c_i=a_i\)

当我们枚举出一个质数\(p_i\)时，我们可以枚举\(j=1\)~\(n\)，然后令\(c_{j\times p_i}+=c_j\)即可

然后我们又发现，不需要这么多个数组，只需要一个数组滚动更新即可

上代码：

#include<bits/stdc++.h>
#define ll unsigned int
using namespace std;
const ll N=2e7+15;
ll n,seed;
ll b[N],ans;
bool np[N];
ll getnext()
{
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}
int main()
{
	scanf("%u %u",&n,&seed);
	for(ll i=1;i<=n;i++) b[i]=getnext();
	np[1]=1;
	for(ll i=1;i<=n;i++)
	{
		if(!np[i])
		for(ll j=1;i*j<=n;j++)
		b[i*j]+=b[j],np[i*j]=1;
		ans^=b[i];
	}
	printf("%u\n",ans);
	return 0;
}