题目

Description

求 $S\left(n\right)={\sum }_{i=1}^{n}f\left(i\right)$S(n)=∑i=1n​f(i)

Solution

part1（核心公式推导）:

对于任何函数 $g\left(i\right)$g(i)，都有：
${\sum }_{i=1}^n(f\ast g)\left(i\right)$∑i=1n​(f∗g)(i)
$={\sum }_{i=1}^n{\sum }_{d\mid i}f\left(d\right)g\left(\frac{i}{d}\right)$=∑i=1n​∑d∣i​f(d)g(di​)
$={\sum }_{i=1}^{n}g\left(i\right){\sum }_{i\ast j\le n}f\left(j\right)$=∑i=1n​g(i)∑i∗j≤n​f(j)
$={\sum }_{i=1}^{n}g\left(i\right)S(\lfloor \frac{n}{i}\rfloor )$=∑i=1n​g(i)S(⌊in​⌋)
那么 $g\left(1\right)S\left(n\right)={\sum }_{i=1}^n(f\ast g)\left(i\right)-{\sum }_{i=2}^{n}g\left(i\right)S(\lfloor \frac{n}{i}\rfloor )$g(1)S(n)=∑i=1n​(f∗g)(i)−∑i=2n​g(i)S(⌊in​⌋)
杜教筛就要构造一个 $g\left(i\right)$g(i)，使得 ${\sum }_{i=1}^n(f\ast g)\left(i\right)$∑i=1n​(f∗g)(i)与 $g\left(i\right)$g(i)能快速计算

part2（复杂度证明）:

假设计算 $S\left(n\right)$S(n)的复杂度为 $T\left(n\right)$T(n)
那么 $T\left(n\right)=O\left(\sqrt{n}\right)+{\sum }_{i=1}^{\sqrt{n}}T\left(i\right)+T\left(\frac{n}{i}\right)$T(n)=O(n ​)+∑i=1n ​​T(i)+T(in​)（ $i$i从 $1$1枚举到 $n$n时所有不同的 $T(\lfloor \frac{n}{i}\rfloor )$T(⌊in​⌋)之和）
据 $tangjz$tangjz大佬所说：这里只展开一层就可以了，更深层的复杂度是高阶小量
所以 $T\left(n\right)={\sum }_{i=1}^{\sqrt{n}}O\left(\sqrt{i}\right)+O\left(\sqrt{\frac{n}{i}}\right)$T(n)=∑i=1n ​​O(i ​)+O(in​ ​)
$={\sum }_{i=1}^{\sqrt{n}}O\left(\sqrt{\frac{n}{i}}\right)$=∑i=1n ​​O(in​ ​)
$=\sqrt{n}{\int }_1^{\sqrt{n}}{x}^{-\frac{1}{2}}dx$=n ​∫1n ​​x−21​dx
$=\sqrt{n}\cdot 2x^{\frac{1}{2}}{\mid }_1^{\sqrt{n}}$=n ​⋅2x21​∣1n ​​
$=O\left(n^{\frac{3}{4}}\right)$=O(n43​)
如果预处理了前 $k(k\ge \sqrt{n})$k(k≥n ​)个数的前缀和，那么
$T\left(n\right)=O\left(k\right)+{\sum }_{i=1}^{\frac{n}{k}}O\left(\sqrt{\frac{n}{i}}\right)=O(k+\frac{n}{\sqrt{k}})$T(n)=O(k)+∑i=1kn​​O(in​ ​)=O(k+k ​n​)
当 $k=O\left(n^{\frac{2}{3}}\right)$k=O(n32​)时 $T\left(n\right)=O\left(n^{\frac{2}{3}}\right)$T(n)=O(n32​)

part3（example）:

就拿 $\phi \left(i\right)$φ(i)举例吧，有一个公式 $\phi \ast 1=i{d}_1$φ∗1=id1​
所以 $1\left(1\right)S\left(n\right)={\sum }_{i=1}^{n}i{d}_1\left(i\right)-{\sum }_{i=2}^{n}1\left(i\right)S(\lfloor \frac{n}{i}\rfloor )$1(1)S(n)=∑i=1n​id1​(i)−∑i=2n​1(i)S(⌊in​⌋)
$S\left(n\right)=\frac{n(n+1)}{2}-{\sum }_{i=2}^{n}S(\lfloor \frac{n}{i}\rfloor )$S(n)=2n(n+1)​−∑i=2n​S(⌊in​⌋)

part4（代码实现中的注意点）:

$1.$1.因为数据不止 $1$1组，所以如果预处理 $k$k个数的话，复杂度为 $O(k+T\frac{n}{\sqrt{k}})$O(k+Tk ​n​)
根据基本不等式， $k$k取 $(Tn{)}^{\frac{2}{3}}$(Tn)32​最为合适
$2.$2.计算 $\frac{n(n+1)}{2}$2n(n+1)​时，因为有 $n+1$n+1，所以可能会爆 $int$int，数论分块中的 $l$l和 $r$r也是如此
$3.$3.关于记忆化，有两种方法。一种是开unordered_map，另外一种是假设现在正在计算 $S\left(n^{\prime }\right)$S(n′)，那么只要判断 $p[\lfloor \frac{n}{n^{\prime }}\rfloor ]$p[⌊n′n​⌋]即可，数组大小可开到 $O\left(\frac{n}{k}\right)的规模$O(kn​)的规模

Code

#include<cstdio>
#include<cstring>
typedef unsigned long long ll;
typedef unsigned int ui;
const int N=5000000;
int T,i,pr[N/14],n,cnt,j,t,mu[N],m[1291],nn;
bool vis[N];
ll phi[N],p[1291];
ll calp(int n){
	if (n<N) return phi[n];
	if (p[nn/n]) return p[nn/n];
	ll ans=(1ll*n+1)*n>>1;
	for (ui l=2,r;l<=n;l=r+1) r=n/(n/l),ans-=calp(n/l)*(r-l+1);
	return p[nn/n]=ans;
}
int calm(int n){
	if (n<N) return mu[n];
	if (m[nn/n]) return m[nn/n];
	int ans=1;
	for (ui l=2,r;l<=n;l=r+1) r=n/(n/l),ans-=calm(n/l)*(r-l+1);
	return m[nn/n]=ans;
}
int main(){
	scanf("%d",&T);
	phi[1]=mu[1]=1;
	for (i=2;i<N;i++){
		if (!vis[i]) pr[cnt++]=i,phi[i]=i-1,mu[i]=-1;
		for (j=0;j<cnt && (t=i*pr[j])<N;j++){
			vis[t]=1;
			if (!(i%pr[j])){
				phi[t]=phi[i]*pr[j];
				mu[t]=0;
				break;
			}
			phi[t]=phi[i]*(pr[j]-1);
			mu[t]=-mu[i];
		}
	}
	for (i=2;i<N;i++) phi[i]+=phi[i-1],mu[i]+=mu[i-1];
	for (;T--;) scanf("%d",&n),nn=n,memset(p,0,sizeof(p)),
	memset(m,0,sizeof(m)),printf("%llu %d\n",calp(n),calm(n));
}