杜教筛_分级筛和振动筛「建议收藏」

杜教筛

首先我们要知道杜教筛是用来求积性函数的前缀和的。

前置知识1：积性函数

若$a$和$b$互质，那么有$f(ab)=f(a)f(b)$，则称$f(x)$为积性函数。
若函数$f(x)$，对于任意两个数$a$和$b$，都有$f(ab)=f(a)f(b)$，则称$f(x)$为完全积性函数

常见的积性函数

• 欧拉函数$\phi (x)$ 比$x$小的与$x$互质的数的个数
• 莫比乌斯函数$\mu (x)=\{\begin{array}{c}1,x=1\\ (-1{)}^k,x=p_1{p}_2\cdots p_k,p_i为不相等的素数\\ 0,x有大于1的平方数因数\end{array}$
• 正因子和$\sigma (x)={\sum }_{d|x}d$
• 正因子个数$\sigma (x)={\sum }_{d|x}1$

常见的完全积性函数

• $ϵ(x)=[x==1]$
• $I(x)=1$
• $id(x)=x$

前置知识2：狄利克雷卷积

定义： 对于两个积性函数$f(n)g(n)$的狄利克雷卷积为$(f\ast g)(i)={\sum }_{d|n}f(d)\ast g(\frac{n}{d})$,也就是对于$i\ast j==n$的整数$i,j$的函数值乘在一起再求和。

狄利克雷卷积满足结合律和交换律
单位函数$ϵ(x)$是狄利克雷卷积的单位元，任何函数卷上$ϵ(x)$都是它本身

一些狄利克雷卷积的结论：
1.$\mu \ast I=ϵ(x)$
2.$\phi \ast I=id(x)$
3.$id\ast \mu =\phi (x)$

前置知识3：莫比乌斯反演

对弈两个积性函数如果有$f=g\ast I$, 则有$g=f\ast \mu$
把卷积拆开，原式为$f(x)={\sum }_{d|x}g(d)$，则有$g(x)={\sum }_{d|x}f(\frac{x}{d})\ast \mu (d)$
证明：
$$f=g\ast I$$
$$f\ast \mu =g\ast I\ast \mu$$
$$f\ast \mu =g\ast ϵ$$
$$f\ast \mu =g$$

杜教筛

我们构造积性函数$f,g$，令$S(n)={\sum }_{i=1}^{n}f(i)$
$$S(n)=\frac{{\sum }_{i=1}^n(f\ast g)(i)-{\sum }_{i=2}^{n}g(i)\ast S(\frac{n}{i})}{g(1)}$$
称此公式为杜教筛公式
证明略

这里放一道洛谷的模板题：传送门

题中的$an{s}_1={\sum }_{i=1}^n\phi (i)$
我们令$$S(n)=\sum _{i=1}^n\phi (i)$$
我们令$g=I$
代入杜教筛公式$$S(n)=\frac{{\sum }_{i=1}^nϵ(i)-{\sum }_{i=2}^{n}I(i)\ast S(\frac{n}{i})}{1}$$
$$S(n)=1-\sum _{i=2}^n\ast S(\frac{n}{i})$$
然后就用数论分块模板求$S(n)$了，但直接这样求显然是做不到线性的复杂度的，所以我们需要预处理出$\mu (i)\phi (i)$，然后对于求过的答案用$map$记录来降低时间复杂度。经过证明，当预处理的值为$n^{\frac{2}{3}}$时，时间复杂度$O(n^{\frac{2}{3}})$。

$ans2$也可以用同样的方法进行化简，最后的式子为
$$S(n)=\frac{n(n+1)}{2}-\sum _{i=2}^n\ast S(\frac{n}{i})$$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define LL __int128;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const double eps = 1e-8;
const int maxn = 5e6 + 10;
const int mod = 1e9 + 7; 
int prime[maxn], mu[maxn], check[maxn];
ll phi[maxn];
unordered_map<ll, int> ans_mu;
unordered_map<ll, ll> ans_phi;
void init() { 
   
	mu[1] = 1;
	phi[1] = 1;
	int tot = 0;
	for(int i = 2; i <= maxn; i++) { 
   
		if(!check[i]) { 
   
			prime[tot++] = i;
			mu[i] = -1;
			phi[i] = i - 1;
		}
		for(int j = 0; j < tot; j++) { 
   
			if(i * prime[j] > maxn) break;
			check[i * prime[j]] = true;
			if(i % prime[j] == 0) { 
   
				mu[i * prime[j]] = 0;
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else{ 
   
				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
				mu[i * prime[j]] = -mu[i];
			}
		}
	}
	for(int i = 1; i <= maxn; i++) { 
   
		mu[i] += mu[i - 1];
		phi[i] += phi[i - 1];
	}
}
int get_mu(ll x) { 
   
	if(x <= maxn) return mu[x];
	if(ans_mu[x]) return ans_mu[x];
	int ans = 1;
	for(ll l = 2, r; l <= x; l = r + 1){ 
   
    	r = x / (x / l);
    	ans -= (r - l + 1) * get_mu(x / l);
	}
	ans_mu[x] = ans;
	return ans;
}
ll get_phi(ll x) { 
   
	if(x <= maxn) return phi[x];
	if(ans_phi[x]) return ans_phi[x];
	ll ans = (ll)(x + 1) * (ll)x / 2;
	for(ll l = 2, r; l <= x; l = r + 1){ 
   
    	r = x / (x / l);
    	ans -= (r - l + 1) * get_phi(x / l);
	}
	ans_phi[x] = ans;
	return ans;
}
void solve(){ 
   
	ll n;
	scanf("%lld", &n);
	printf("%lld %d\n", get_phi(n), get_mu(n));
}
int main() { 
   
	init();
	int t = 1;
	scanf("%d", &t);
	// cin>>t;
	while(t--)
		solve();
	PAUSE;
	return 0;
}

今天的文章杜教筛_分级筛和振动筛「建议收藏」分享到此就结束了，感谢您的阅读。