杜教筛入门

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142208852

求 ff 的前缀和（不要求 ff 为积）

考虑 h=f∗gh=f*g ，若 h,gh,g 前缀和都好求，那 ff 的前缀和 ss 是好求的

∑i=1nhi=∑ij≤nfigj\sum_{i=1}^n h_i=\sum_{ij\le n}f_ig_j

∑i=1nhi=∑i≤ngi∑d=1⌊ni⌋fd\sum_{i=1}^n h_i=\sum_{i\le n}g_i\sum_{d=1}^{\left \lfloor\frac ni\right \rfloor}f_d

∑i=1nhi=∑i≤ngis(⌊ni⌋)\sum_{i=1}^n h_i=\sum_{i\le n}g_is(\left \lfloor\frac n i\right \rfloor)

若满足 g1≠0g_1\ne 0 ，则：

s(n)=∑i=1nhi−∑d=2ngis(⌊nd⌋)g1s(n)=\frac{\sum_{i=1}^nh_i-\sum_{d=2}^ng_is(\left \lfloor\frac n d\right \rfloor)}{g_1}

我们计算时直接整除分块即可

加速：根号分治

求 s(x)s(x) 时，对于 x≤Bx\le B ，我们直接线性筛预处理。

对于 x>Bx>B 时，我们记忆化。注意到所有遍历的 xx 满足 ⌊nx⌋\left \lfloor\dfrac n x\right \rfloor 互不相同，所以直接拿数组来存即可。

可以证明在 B=n23B=n^{\frac 2 3} 时可以达到最优复杂度 O(23)O(\frac 2 3)

杜教筛的难度就是构造 g,hg,h ，剩下直接套式子就行了。

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 1000000
int n, m, i, j, k, T;
int mu[N], pri[N], L, ans1, ans2; 
int z[N], top, smu[N]; 
int sph[N], phi[N]; 
map<int, int>Phi, Mu; 

int find_mul(int n) {
	if(n <= L) return smu[n]; 
	if(Mu[n]) return Mu[n]; 
	int ans = 1, l, r; 
	for(l = 2, r = 0; l <= n; l = r + 1) {
		r = min(n, n / (n / l));
//		debug("%lld --> %lld\n", n / l, n); 
		ans -= find_mul(n / l) * (r - l + 1); 
	}
	return Mu[n] = ans; 
}

int find_phi(int n) {
	if(n <= L) return sph[n]; 
	if(Phi[n]) return Phi[n]; 
	int ans = (n + 1) * n / 2, l, r; 
	for(l = 2, r = 0; l <= n; l = r + 1) {
		r = min(n, n / (n / l));
//		debug("%lld --> %lld [%lld]\n", n / l, n, r - l + 1); 
		ans -= find_phi(n / l) * (r - l + 1); 
	}
//	debug("Phi[%lld] = %lld\n", n, ans); 
	return Phi[n] = ans; 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	L = N - 1; 
		memset(pri, -1, sizeof(pri)); 
//		memset(mu, 0, sizeof(mu)); 
//		memset(smu, 0, sizeof(smu)); 
//		memset(phi, 0, sizeof(phi)); 
//		memset(Phi, 0, sizeof(Phi)); 
//		memset(sph, 0, sizeof(sph)); 
//		memset(Mu, 0, sizeof(Mu)); 
		top = 0; 
		mu[1] = smu[1] = phi[1] = sph[1] = 1; pri[1] = 0; 
		for(i = 2; i <= L; ++i){
			if(pri[i]) {
				z[++top] = i; mu[i] = -1; phi[i] = i - 1; 
			}
			for(j = 1; j <= top && i * z[j] <= L; ++j) {
				int x = i * z[j]; pri[x] = 0; 
				mu[x] = mu[z[j]] * mu[i]; 
				phi[x] = phi[z[j]] * phi[i]; 
				if(i % z[j] == 0) { 
					phi[x] = phi[i] * z[j]; 
					mu[x] = 0; break; 
				}
			}
			smu[i] = smu[i - 1] + mu[i]; 
			sph[i] = sph[i - 1] + phi[i]; 
//			debug("mul[%lld] = %lld %lld\n", i, mu[i], smu[i]); 
//			debug("phi[%lld] = %lld %lld\n", i, phi[i], sph[i]); 
		}
	T=read();
	while(T--) {
		n = m = read(); 
		ans1 = find_phi(n); 
		ans2 = find_mul(n); 
		printf("%lld %lld\n", ans1, ans2); 
	}
	
	return 0;
}