学习笔记 - Diriclet前缀和 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

学习笔记 - Diriclet前缀和

发表于 分类于 Valine：

算是一个小知识点，并不算难

# 例题

因为这个知识点很小，就直接从例题切入。

点击展开/折叠 题面

给定 $n$（$n\le2\times10^7$）和一个长度为 $n$ 的数列 $a_1,a_2,\dots,a_n$，求数列 ${b_n}$

$$b_n=\sum_{d\mid n}a_d\bmod2^{32}$$

输出 ${b_n}$ 的异或和。

# $O(n\ln n)$ 的算法

不直接计算 $b_i$ 而是考虑 $a_i$ 对每个 $b_i$ 的贡献。

按照题意，$a_i$ 会对每个 $i$ 的倍数 $k$ 对应的 $b_k$ 产生一次贡献，因此枚举 $i$ 再枚举 $i$ 的倍数 $k$，更新 $b_k$。

根据调和级数，这样复杂度为 $O(n\ln n)$，并卡不过此题。

# $O(n\ln\ln n)$ 的算法

考虑“$k$ 是 $i$ 的倍数”的实质。

将 $k$ 和 $i$ 分别作唯一分解 $k=\prod p_i^{a_i},i=\prod p_i^{b_i}$，则当 $\forall_i a_i\ge b_i$ 成立时，$k$ 是 $i$ 的倍数。

设下标的唯一分解中最大的质因子为 $p_m$。那么把 $i$ 看作 $m$ 维空间中的一个点 $(b_1,b_2,\dots,b_m)$，则其倍数 $k$ 对应的点的每一维都不低于 $i$。

于是类似于二维前缀和，$b_k$ 相当于是在 $m$ 维空间内对 $a_i$ 作高维前缀和。

以每个质因子为元，求高维前缀和可以从小到大枚举质数 $p_i$，再枚举数 $j$，更新 $p_ij$。具体实现类似埃氏筛：

线筛素数后时间复杂度可达到 $O(n\ln\ln n)$但是我不会证，反正跑得飞快就对了。

除此之外还有所谓“后缀和”，如果 $b_i=\sum_{i\mid d}a_d$，相当于是在 $m$ 维空间内求后缀和，所以真就倒过来写（

# 另一例题

给定 $n,P$，求：

要用比 $O(n\log n)$ 更快的做法。

把乘上的 $\sigma_0(\gcd(i,j))$ 看作一个系数，即 $\sigma_0(i)\sigma_0(j)$ 对答案贡献了 $\sigma_0(\gcd(i,j))$ 次，于是原式可以枚举 $\gcd$ 的值从而表示为：

如果能快速计算 $\sum_{d\mid i}\sigma_0(i)$ 就可以解决本题了。非常显然是一个 Diriclet 后缀和，先线筛出 $\sigma_0(i)$，然后套用后缀和的板子即可。

# 源代码

- 例题1

> Linked 洛谷P5495

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef unsigned int ui;
const int N=2e7;

int n,nprm;
ui seed,key[N];
int prm[N/10];
bool vis[N];

inline ui Key(){
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}

void Sieve(){
	for(int i=2;i<=n;i++){
		if(!vis[i]) prm[++nprm]=i;
		for(int j=1;j<=nprm && prm[j]*i<=N;j++){
			vis[prm[j]*i]=true;
			if(i%prm[j]==0) break;
		}
	}
}
int main(){
	cin>>n>>seed;
	Sieve();
	for(int i=1;i<=n;i++) key[i]=Key();
	for(int i=1;i<=nprm;i++)
		for(int j=1;j*prm[i]<=n;j++)
			key[j*prm[i]]+=key[j];
	ui ans=0;
	for(int i=1;i<=n;i++) ans^=key[i];
	cout<<ans<<endl;
	return 0;
}

- 例题2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define ci const int &
const int N=5e7+10;

int n,nprm,MOD;
int prm[N/10],dv[N];
bool vis[N];

inline int Add(ci a,ci b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return 1ll*a*b%MOD;}
void Sieve(){
	dv[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]) prm[++nprm]=i,dv[i]=2;
		for(int j=1;j<=nprm && prm[j]*i<=n;j++){
			vis[i*prm[j]]=true;
			dv[i*prm[j]]=2*dv[i];
			if(i%prm[j]==0){
				dv[i*prm[j]]-=dv[i/prm[j]];
				break;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&MOD);
	Sieve();
	for(int i=1;i<=nprm;i++)
		for(int j=n/prm[i];j;j--)
			dv[j]=Add(dv[j],dv[j*prm[i]]);
	int ans=0;
	for(int i=1;i<=n;i++) ans=Add(ans,Mul(dv[i],dv[i]));
	printf("%d\n",ans);
	return 0;
}

THE END

Thanks for reading!

> Linked hello&bye，days-网易云