杜教筛练习题

前置知识：杜教筛

题目大意

给定$n$，求

$$\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n\varphi (\gcd (i,j,k))$$

输出其结果模$20230923$后的值。

$1\le n\le 10^9$

题解

令$d=\gcd (i,j,k)$，则

$$\begin{array}{rl}\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n\varphi (\gcd (i,j,k))& =\sum _{d=1}^n\varphi (d)\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n[\gcd (i,j,k)==d]\\ & \\ & =\sum _{d=1}^n\varphi (d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }[\gcd (i,j,k)==1]\\ & \\ & =\sum _{d=1}^n\varphi (d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{k=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{t|i,t|j,t|k}\mu (t)\\ & \\ & =\sum _{d=1}^n\varphi (d)\sum _{t=1}^{\lfloor \frac{n}{d}\rfloor }\mu (t)\times \lfloor \frac{n}{d}{\rfloor }^3\end{array}$$

其中$\sum _{t=1}^{\lfloor \frac{n}{d}\rfloor }\mu (t)\times \lfloor \frac{n}{d}{\rfloor }^3$可以用杜教筛来求。设$g(t)=\sum _{t=1}^{\lfloor \frac{n}{d}\rfloor }\mu (t)\times \lfloor \frac{n}{d}{\rfloor }^3$，则整个式子为$\sum _{d=1}^n\varphi (d)\times g(\lfloor \frac{n}{d}\rfloor )$，也是可以用杜教筛来求。

求$\varphi (d)$和$\mu (t)$前缀和的杜教筛都是$O(n^{\frac{2}{3}})$的（求$\mu (t)$的杜教筛总体来说可以看做一次数论分块），再来看看枚举的时间复杂度。

枚举的次数可以分为在数论分块值$\le \sqrt{n}$和数论分块值$>\sqrt{n}$两个部分。

对于第一部分，第$i$次外部的数论分块的范围为$\frac{n}{i}$，内部的枚举次数为$\sqrt{\frac{n}{i}}$，枚举次数是$\sum _{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i}}$

$\sum _{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i}}=\sqrt{n}(\sum _{i=1}^{\sqrt{n}}\sqrt{\frac{1}{i}})\approx \sqrt{n}{\int }_0^{\sqrt{n}}{x}^{-\frac{1}{2}}dx=\sqrt{n}\times 2x^{\frac{1}{2}}{|}_0^{\sqrt{n}}=\sqrt{n}\times 2x^{\frac{1}{4}}=2n^{\frac{3}{4}}$

对于第二部分，总共有$\sqrt{n}$个数论分块值，则枚举次数为$\sum _{i=1}^{\sqrt{n}}\sqrt{i}$

$\sum _{i=1}^{\sqrt{n}}\sqrt{i}\approx {\int }_0^{\sqrt{n}}{x}^{\frac{1}{2}}dx=\frac{2}{3}{x}^{\frac{3}{2}}{|}_0^{\sqrt{n}}=\frac{2}{3}{n}^{\frac{3}{4}}$

所以，总时间复杂度为$O(n^{\frac{3}{4}})$。

code

#include
using namespace std;
const int N=10000000;
const long long mod=20230923;
int z[N+5],p[N+5];
long long ans=0,ph[N+5],sph[N+5],mu[N+5],smu[N+5];
map<long long,long long>mph,mmu;
void init(){
	z[1]=ph[1]=mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!z[i]){
			p[++p[0]]=i;
			ph[i]=i-1;
			mu[i]=-1;
		}
		for(int j=1;j<=p[0]&&i*p[j]<=N;j++){
			z[i*p[j]]=1;
			if(i%p[j]==0){
				ph[i*p[j]]=ph[i]*p[j];
				break;
			}
			ph[i*p[j]]=ph[i]*ph[p[j]];
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++){
		sph[i]=(sph[i-1]+ph[i])%mod;
		smu[i]=(smu[i-1]+mu[i])%mod;
	}
}
long long djs1(long long t){
	if(t<=N) return sph[t];
	if(mph.count(t)) return mph[t];
	long long re=0;
	for(long long l=2,r;l<=t;l=r+1){
		r=t/(t/l);
		re=(re+(r-l+1)*djs1(t/l)+mod)%mod;
	}
	re=(t*(t+1)/2-re+mod)%mod;
	mph[t]=re;
	return re;
}
long long djs2(long long t){
	if(t<=N) return smu[t];
	if(mmu.count(t)) return mmu[t];
	long long re=0;
	for(long long l=2,r;l<=t;l=r+1){
		r=t/(t/l);
		re=(re+(r-l+1)*djs2(t/l)+mod)%mod;
	}
	re=(1-re+mod)%mod;
	mmu[t]=re;
	return re;
}
long long gt(long long t){
	long long re=0;
	for(long long l=1,r;l<=t;l=r+1){
		r=t/(t/l);
		re=(re+(djs2(r)-djs2(l-1)+mod)%mod*(t/l)%mod*(t/l)%mod*(t/l)%mod)%mod;
	}
	return re;
}
int main()
{
	long long n;
	scanf("%lld",&n);
	init();
	for(long long l=1,r;l<=n;l=r+1){
		r=n/(n/l);
		ans=(ans+(djs1(r)-djs1(l-1)+mod)%mod*gt(n/l)%mod)%mod;
	}
	printf("%lld",ans);
	return 0;
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74