前置知识

莫比乌斯反演

莫比乌斯反演

数论函数

积性函数

若 \(gcd(a,b)=1\)，则\(f(a \times b)=f(a) \times f(b)\)

完全积性函数

去掉 \(gcd(a,b)=1\) 的条件

常见的积性函数

恒等函数：\(I(n)=1\)

单位函数：\(id(n)=n\)

元函数：\(\epsilon(n)=[n=1]\)

(以上三个函数也是完全积性函数)

欧拉函数：\(\varphi(n)\):小于 \(n\) 和 \(n\) 互质的自然数个数

莫比乌斯函数：\(\mu(n)\)

约数和函数：\(\sigma_k(n)\) 表示 \(n\) 的所有因数的 \(k\) 次方之和

狄利克雷卷积

定义

两个函数 \((f,g)\) 的狄利克雷卷积记为 \(f*g\)

\((f * g)(n)=\sum_{k \mid n} f(k) \times g\left(\frac{n}{k}\right)\)

性质

\(1\)、交换律 \(f*g=g*f\)

\(2\)、结合律 \(f*(g*h)=(f*g)*h\)

\(3\)、分配律 \(f*h+g*h=(f+g)*h\)

\(4\)、若 \(f,g\) 为积性函数，则 \(f*g\) 也是积性函数

常用卷积式

\(1\)、\(\mu*I=\epsilon\)

即 \(\sum_{d|n}\mu(d)=[n=1]\)

也就是莫比乌斯函数性质一

\(2\)、\(\mu*id=\varphi\)

即 \(\sum_{d|n}\mu(d)\frac{n}{d}=\varphi(n)\)

也就是莫比乌斯函数性质二

\(3\)、\(\varphi * I=id\)

即 \(\sum_{d|n}\varphi(d)=n\)

杜教筛

可以在低于线性的时间内筛出积性函数的前缀和

如果我们要筛的积性函数为 \(f\)

那么杜教筛的核心就是构造两个积性函数\(h,g\)，使得 \(h=f*g\)

并且 \(h\) 和 \(g\) 的前缀和能够快速地求出来

首先我们要用线性筛筛出一部分函数值，之后递归的时候要用到

设 \(s(n)=\sum\limits_{i=1}^nf(i)\)则

\(\begin{aligned} \sum\limits_{i=1}^n(f*g)(i) &=\sum\limits_{i=1}^n\sum_{d|i}f(d)g(\frac{d}{i}) \\&=\sum\limits_{d=1}^ng(d)\sum_{i=1}^{\frac{n}{d}} f(i)\\ &=\sum\limits_{d=1}^ng(d)s(\frac{n}{d}) \\ &=g(1)s(n)+\sum\limits_{d=2}^ng(d)s(\frac{n}{d}) \end{aligned}\)

所以

\(s(n)g(1)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{d=2}^ng(d)s(\frac{n}{d})\)

这样，我们就得到了一个关于 \(s(n)\) 的表达式

前半部分是 \(h\) 函数的前缀和，可以快速得到

后半部分可以进行整除分块递归求解，递归的时候要记忆化

最后再整体除一个 \(g(1)\) 即可

时间复杂度 \(O(n^{\frac{2}{3}})\)

杜教筛能够筛的积性函数不是很多

主要是配合莫比乌斯反演使用

筛 \(\mu\) 函数时利用 \(\mu*I=\epsilon\)

筛 \(\varphi\) 函数时利用 \(\varphi * I=id\)

因此需要掌握一些常见的前缀和的公式

代码

P4213 【模板】杜教筛（Sum）

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
typedef long long ll;
const int maxn=5e6+5,mmax=5e6,mod=1e6+3;
int pri[maxn];
ll mu[maxn],phi[maxn];
bool not_pri[maxn];
struct has{
	struct asd{
		int nxt,num;
		ll val;
	}b[maxn];
	int h[maxn],tot;
	has(){
		memset(h,-1,sizeof(h));
		tot=1;
	}
	void insert(rg int num,rg ll val){
		rg int now=num%mod;
		b[tot].nxt=h[now];
		b[tot].val=val;
		b[tot].num=num;
		h[now]=tot++;
	}
	ll cx(rg int num){
		rg int now=num%mod;
		for(rg int i=h[now];i!=-1;i=b[i].nxt){
			if(b[i].num==num) return b[i].val;
		}
		return -1;
	}
}ans_phi,ans_mu;
void xxs(){
	not_pri[0]=not_pri[1]=1;
	mu[1]=phi[1]=1;
	for(rg int i=2;i<=mmax;i++){
		if(!not_pri[i]){
			pri[++pri[0]]=i;
			mu[i]=-1;
			phi[i]=i-1;
		}
		for(rg int j=1;j<=pri[0] && 1LL*i*pri[j]<=mmax;j++){
			not_pri[i*pri[j]]=1;
			if(i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j];
				mu[i*pri[j]]=0;
				break;
			} else {
				phi[i*pri[j]]=phi[i]*phi[pri[j]];
				mu[i*pri[j]]=-mu[i];
			}
		}
	}
	for(rg int i=1;i<=mmax;i++){
		mu[i]+=mu[i-1];
		phi[i]+=phi[i-1];
	}
}
ll getsum_mu(rg int now){
	if(now<=mmax) return mu[now];
	if(ans_mu.cx(now)!=-1) return ans_mu.cx(now);
	ll ans=1;
	for(rg int l=2,r=0;r<now;l=r+1){
		r=now/(now/l);
		ans-=1LL*(r-l+1)*getsum_mu(now/l);
	}
	ans_mu.insert(now,ans);
	return ans;
}
ll getsum_phi(rg int now){
	if(now<=mmax) return phi[now];	
	if(ans_phi.cx(now)!=-1) return ans_phi.cx(now);
	ll ans=1LL*now*(now+1LL)/2;
	for(rg int l=2,r=0;r<now;l=r+1){
		r=now/(now/l);
		ans-=1LL*(r-l+1)*getsum_phi(now/l);
	}
	ans_phi.insert(now,ans);
	return ans;
}
int t,n;
int main(){
	xxs();
	t=read();
	while(t--){
		n=read();
		printf("%lld %lld\n",getsum_phi(n),getsum_mu(n));
	}
	return 0;
}