「从零开始的莫比乌斯反演 & 杜教筛」

无聊开个坑……为了学弟的数论提前做好准备。
本文的写作目的是在你只接触过一点数论的情况下教会你莫比乌斯反演和杜教筛……
顺便加深一下我的理解。

下文规定,[P][P] 表示,若 PP 成立,[P]=1[P]=1,否则 [P]=0[P]=0

数论分块

之所以要放到这里讲,是因为……不知道。

数论分块可以在 O(n)O(\sqrt n) 的复杂度内计算 i=1nf(i)g(ni)\sum\limits_{i=1}^n f(i)g(\lfloor\frac ni\rfloor) 的值,但前提是可以求出 f(i)f(i) 的前缀和并算出所有 g(ni)(1in)g(\lfloor\frac ni\rfloor)\,(1\le i\le n)
简单地说,就是,打表可以发现,ni\lfloor\frac ni\rfloor 有很多连续的相同段,故可以用乘法分配律把相同的段放在一起算,那么复杂度应该就是段数。

然后有一个结论,ni(1in)\lfloor\frac ni\rfloor\,(1\le i\le n) 的取值只有 O(n)O(\sqrt n) 种(2n2\sqrt n 种左右)。
证明:
分类讨论。
ini \le \sqrt n,则此时的 ii 只有 O(n)O(\sqrt n) 种,ni\lfloor\frac ni\rfloor 自然也只有 O(n)O(\sqrt n) 种。
i>ni > \sqrt n,则易得 ni<n\frac ni < \sqrt n,此时 ni\lfloor\frac ni\rfloor 也只有 O(n)O(\sqrt n) 种。
故结论成立。

于是,如果要实现程序,需要知道每一段的最右端,即在给定 ii 的情况下求得满足 ni=nx\lfloor\frac ni\rfloor = \lfloor\frac nx\rfloor 的最大的正整数 xx
又一个结论:x=nnix = \lfloor\frac n{\lfloor\frac ni\rfloor}\rfloor
证明:
由于 ni=nx\lfloor\frac ni\rfloor = \lfloor\frac nx\rfloor,故 ninx<ni+1\lfloor\frac ni\rfloor \le \frac nx < \lfloor\frac ni\rfloor+1
故有 nni+1<xnni\frac n{\lfloor\frac ni\rfloor+1} < x \le \frac n{\lfloor\frac ni\rfloor}
xx 最大,即为 nni\lfloor \frac n{\lfloor\frac ni\rfloor}\rfloor
证毕。

参考代码

1
2
3
4
5
for(int l = 1,r;l <= n;l = r + 1)
{
r = n / (n / l);
//do sth with [l,r]...
}

筛法

埃氏筛

埃氏筛的起源是,首先假设 [2,n][2,n] 以内的整数都是质数,然后对于每个数,枚举其除了自身以外的倍数,并把其标记为合数。
最后得到的就是质数了。

然而这样子非常的慢……
根据调和级数,复杂度是 O(i=1nni)=O(nlogn)O(\sum\limits_{i=1}^n \frac ni) = O(n \log n)

于是,埃氏筛就出现了:只枚举素数的倍数。
这个比较显然,对于合数 ii,其倍数 dd,也是 ii 的因数的倍数,故合数的倍数均已经被筛过。

以上就是埃氏筛的主要思想,但是实际实现的时候,我们一般枚举 ii 的倍数的时候,会从 i2i^2 开始筛,因为其以下的倍数都已经被筛过了。

时间复杂度

埃氏筛的复杂度为 O(nloglogn)O(n \log \log n)

证明如下(可以跳过):
i1i-1 个素数可以近似地表示为 ilnii \ln i
π(n)\pi(n)nn 以内的素数个数)也可以近似地表示为 nlnn\frac n{\ln n}
故算法的复杂度为

O(i=2nlnn+1nilni)=O(2nlnnnxlnxdx)=O(nlnlnn)=O(nloglogn)O(\sum\limits_{i=2}^{\lfloor\frac n{\ln n}\rfloor + 1} \frac n{i \ln i}) = O(\int_2^{\frac n{\ln n}} \frac n{x \ln x}\text{d}x) = O(n \ln \ln n) = O(n \log \log n)

实际上这个复杂度并没有考虑到从平方开始枚举倍数的优化。

欧拉筛 / 线性筛

从名字就能看出来这个算法是线性的。

注意到埃氏筛优化之后仍然会有重复筛到的数。
于是欧拉筛的思想就是:令每个数被其最小质因子筛到。
这样就有了代码实现的问题。

于是,我们原来是枚举质数 ii,然后枚举其倍数 ij(1jni)ij\,(1 \le j \le \frac ni)
现在我们换个顺序,先枚举这个 jj,然后再枚举一个质数 i(1ini)i\,(1 \le i \le \frac ni)

那么,令 jj 的最小质因子为 pp,则对于 ipi \le pii 显然都是 ijij 的最小质因子。
而对于 i>pi > p,则 ijij 的最小质因子为 pp,故此时可以退出。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
const int N = 1e7;
int n;
int vis[N + 5],cnt,prime[N + 5];
int main()
{
scanf("%d",&n);
for(int i = 2;i <= n;++i)
{
if(!vis[i])
prime[++cnt] = i;
for(int j = 1;j <= cnt && i * prime[j] <= n;++j)
{
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
for(int i = 1;i <= cnt;++i)
printf("%d ",prime[i]);
}

上述代码输出了给定的正整数 nn 以内的所有质数,其中 n107n \le 10^7

时间复杂度

从代码似乎不能明显地看出复杂度,然而根据其思想,容易得到其复杂度为 O(n)O(n)

数论函数

定义

数论函数指定义域为正整数,值域为复数的函数。
在一些文献里也叫做算术函数。

积性函数

本来还有个加性函数,这里略过。

对于一个数论函数 ff,若对于所有 gcd(x,y)=1\gcd(x,y)=1 都有 f(xy)=f(x)f(y)f(xy) = f(x)f(y) 成立,则称 ff 是一个积性函数。
特别地,若 ff 对于所有 x,yx,y 都满足上式,则称 ff 为完全积性函数。

易知积性函数 ff 一定满足 f(1)=1f(1) = 1

常见的积性函数有:

  • 元函数:ϵ(n)=[n=1]\epsilon(n) = [n = 1]
  • 单位函数:
  • 标号函数:
  • 约数函数:σk(n)=dndk\sigma_k(n) = \sum\limits_{d|n} d^k
  • 欧拉函数:φ(n)=i=1n[gcd(i,n)=1]\varphi(n) = \sum\limits_{i=1}^n [\gcd(i,n)=1]
  • 莫比乌斯函数: ,其中 ω(n)\omega(n) 表示 nn 的不同质因子个数。

(比较显然的)性质

f,gf,g 为积性函数,则:

  • h(x)=f(xC)h(x) = f(x^C)
  • h(x)=fC(x)h(x) = f^C(x)
  • h(x)=f(x)g(x)h(x) = f(x)g(x)
  • h(x)=dxf(x)g(xd)h(x) = \sum\limits_{d|x} f(x)g(\frac xd)

都是积性函数。

欧拉函数

定义:φ(n)=i=1n[gcd(i,n)=1]\varphi(n) = \sum\limits_{i=1}^n[\gcd(i,n)=1]

通式

对于 n>1n > 1,令 n=i=1mpicin = \prod\limits_{i=1}^m p_i^{c_i},其中 pip_i 为互不相同的质数(即分解质因数)。
φ(n)=ni=1m(11pi)\varphi(n) = n \prod\limits_{i=1}^m (1 - \frac 1{p_i})

证明:考虑容斥。
首先假设前 nn 个正整数都与 nn 互质,然后从中减去 p1p_1 的倍数,p2p_2 的倍数……pmp_m 的倍数。
但是这样会重复减 p1,p2p_1,p_2 的公倍数,p1,p3p_1,p_3 的公倍数……pm1,pmp_{m-1},p_m 的公倍数,于是再加回来。
然而又会重复加 p1,p2,p3p_1,p_2,p_3 的公倍数,p1,p2,p4p_1,p_2,p_4 的公倍数……pm2,pm1,pmp_{m-2},p_{m-1},p_m 的公倍数,于是再减去。
……

注意到前 nn 个正整数中 ii 的倍数的个数为 ni\lfloor\frac ni\rfloor,而以上的 ii 都为 nn 的因子,取整符号可去掉。

然后,就是欧拉函数通式推导的神奇的一步。
注意到每一项的符号取决于分母是多少个质因子的乘积,故可以视作是若干个 1pi-\frac 1{p_i} 的乘积乘 nn 的结果。

φ(n)=ni=1m(11pi)\varphi(n) = n\prod\limits_{i=1}^m(1 - \frac1{p_i})

由上式易得欧拉函数为积性函数。

性质及证明

欧拉定理

gcd(a,n)=1\gcd(a,n) = 1,则有

严谨的证明要牵扯到各种剩余系之类的名词,这里用一种比较通俗的说法代替。
证明:
为前 nn 个正整数中与 nn 互质的 φ(n)\varphi(n) 个数。
再令 yi=axiy_i = a \cdot x_i

这里要先证明两个性质:


  1. 反证法。假设存在
    则根据同余式的性质与 gcd(a,n)=1\gcd(a,n) = 1,有
    但由于 1xi<n1 \le x_i < n,易知假设不成立。

  2. 由于 yi=axiy_i = a \cdot x_i,又因为 gcd(a,n)=gcd(xi,n)=1\gcd(a,n) = \gcd(x_i,n) = 1,又根据欧几里得算法,原式显然成立。

根据上述两个性质可得

证毕。

nn 为质数时,φ(n)=n1\varphi(n) = n-1,就等价于费马小定理。
由欧拉定理可以导出

扩展欧拉定理

对于任意的 a,na,nbφ(n)b \ge \varphi(n),有

证明:
n=pcsn = p^c \cdot s,其中 pp 为一个质数,gcd(pc,s)=1\gcd(p^c,s)=1(即提取 nn 的一个质因子)。
根据欧拉定理,有
而由于欧拉函数具有积性,可得 ,故
pφ(s)=xs+1p^{\varphi(s)} = xs + 1,则 pφ(s)+c=xn+pcp^{\varphi(s) + c} = xn + p^c

根据以上过程同样可证
bcb \ge c 时,
而由于 cφ(n)c \le \varphi(n),当 b2φ(n)b \ge 2\varphi(n) 时,

对于 aa 的一个质因子 pp,当 ,根据以上过程可得 成立;当 ,根据欧拉定理同样可得上式成立。
故原式成立。
证毕。

其他(比较显然的)性质

  • φ(pc)=pcpc1\varphi(p^c) = p^c - p^{c-1},其中 pp 为质数。
  • ,其中 pp 为质数。
    由通式显然易得。
    由这条性质可以得出线性筛欧拉函数的方法。
  • 对于 n>2n > 2
    由更相减损术(gcd(n,i)=gcd(n,ni)(n>i)\gcd(n,i) = \gcd(n,n-i)\,(n > i))可得。
  • i=1n[gcd(i,n)=1]i=φ(n)n+[n=1]2\sum\limits_{i=1}^n [\gcd(i,n)=1]i = \frac{\varphi(n)n + [n=1]}{2}
    同样由更相减损术可得,对于 n>1n > 1,与 nn 互质的数是成对出现的。
  • dnφ(d)=n\sum\limits_{d|n} \varphi(d) = n
    证明:
    将前 nn 个正整数按与 nngcd\gcd 分类,则由于每个数与 nngcd\gcd 是唯一的,有 n=dni=1n[gcd(i,n)=d]n = \sum\limits_{d|n} \sum\limits_{i=1}^n [\gcd(i,n)=d]
    i=1n[gcd(i,n)=d]=di[gcd(i,n)=d]=i=1nd[gcd(i,n)=1]=φ(nd)\sum\limits_{i=1}^n [\gcd(i,n)=d] = \sum\limits_{d|i} [\gcd(i,n)=d] = \sum\limits_{i=1}^{\frac nd} [\gcd(i,n)=1] = \varphi(\frac nd)
    其中用到了 gcd(agcd(a,b),bgcd(a,b))=1\gcd(\frac a{\gcd(a,b)},\frac b{\gcd(a,b)}) = 1 这个性质,用反证法易证。

欧拉反演

虽然是个假名字,但还挺有用的。
即利用 dnφ(d)=n\sum\limits_{d|n} \varphi(d) = n 这条性质。
之所以叫欧拉反演,因为它可以用来做一些莫反的题,但局限性很强。

例:求 i=1nj=1ngcd(i,j)\sum\limits_{i=1}^n \sum\limits_{j=1}^n \gcd(i,j)
则以 dnφ(d)=n\sum\limits_{d|n} \varphi(d) = n 代入其中的 gcd(i,j)\gcd(i,j) 项可得 i=1nj=1ndgcd(i,j)φ(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{d|\gcd(i,j)} \varphi(d)
接下来是反演题推导的一个常用套路:交换求和号。
一般的策略即在枚举约数时,考虑枚举约数,再考虑其倍数与其产生的贡献。

注意到 等价于 ,并且 i,ji,j 的枚举之间互不影响,由乘法原理可得

看起来这个式子依然要 O(n)O(n) 来做。
但是,如果利用上文中提到的数论分块的技巧(f(n)=φ(n),g(n)=n2f(n) = \varphi(n),g(n) = n^2),可以把复杂度降到 O(n)O(\sqrt n)(前提是线性筛出了欧拉函数的前缀和)。

莫比乌斯函数

莫比乌斯函数的定义式为 ,其中 ω(n)\omega(n) 表示 nn 的不同质因子个数。
有的文献中也把定义式写作:设 n=i=1mpicin = \prod\limits_{i=1}^m p_i^{c_i},则 μ(n)={1,n=10, ci>1(1)m, ci=1\mu(n) = \begin{cases}1,&n=1\\0,&\exists\ c_i>1\\(-1)^m,&\forall\ c_i=1\end{cases}
其实两者是等价的。

一个重要的性质

dnμ(d)=[n=1]\sum\limits_{d|n} \mu(d) = [n=1]
其实类似这种东西的证明可以根据积性,分解质因数后证明对于质数的幂成立,并证明原式。
这样子比较套路,这里有另外一种证明。

对于 n=1n=1,原式显然成立。
对于 n>1n>1,注意到若 dd 有完全平方数因子(简称为平方因子),则 μ(d)=0\mu(d)=0
故有贡献的 dd 肯定得在 nn 的所有质因子中,每个至多取一个,然后乘起来得到。
此时 μ(d)=(1)ω(d)\mu(d) = (-1)^{\omega(d)}
dnμ(d)=i=1ω(n)Cω(n)i(1)i\sum\limits_{d|n}\mu(d) = \sum\limits_{i=1}^{\omega(n)} C_{\omega(n)}^i (-1)^i
由二项式定理((a+b)k=i=1kCkiaibki(a+b)^k = \sum\limits_{i=1}^k C_k^ia^ib^{k-i})可知 i=1ω(n)Cω(n)i(1)i=i=1ω(n)Cω(n)i1ω(n)i(1)i=(11)ω(n)=0\sum\limits_{i=1}^{\omega(n)} C_{\omega(n)}^i (-1)^i = \sum\limits_{i=1}^{\omega(n)} C_{\omega(n)}^i 1^{\omega(n)-i}(-1)^i = (1-1)^{\omega(n)} = 0
证毕。

为什么称它为一个重要的性质呢,因为莫比乌斯反演的证明需要用到这个性质,所以它可以看作一个引理。
但这个引理的用途不止这点。

莫比乌斯反演

若有数论函数 f,Ff,F 满足 F(n)=dnf(d)F(n) = \sum\limits_{d|n} f(d),则 f(n)=dnμ(nd)F(d)f(n) = \sum\limits_{d|n} \mu(\frac nd)F(d)
以上即莫比乌斯反演公式。

证明:
F(n)=dnf(d)F(n) = \sum\limits_{d|n} f(d) 代入上式,可得 dnμ(nd)kdf(k)\sum\limits_{d|n} \mu(\frac nd)\sum\limits_{k|d} f(k)
考虑将 kk 提到最前面,即 knf(k)kd,dnμ(nd)\sum\limits_{k|n} f(k)\sum\limits_{k|d,d|n} \mu(\frac nd)
d=dkd = d' \cdot k,则由 dkn,knd'\cdot k | n,k | n 可得 dnkd' | \frac nk
knf(k)kd,dnμ(nd)=knf(k)dnkμ(ndk)\sum\limits_{k|n} f(k)\sum\limits_{k|d,d|n} \mu(\frac nd) = \sum\limits_{k|n} f(k)\sum\limits_{d'|\frac nk} \mu(\frac n{d'k})
注意到 dnkμ(ndk)=dnk=[nk=1]=[n=k]\sum\limits_{d'|\frac nk} \mu(\frac n{d'k}) = \sum\limits_{d'|\frac nk} = [\frac nk=1] = [n=k]
故原式成立。

不过一般会用到的是莫比乌斯反演公式的另一种形式:若 F(n)=ndf(d)F(n) = \sum\limits_{n|d} f(d),则 f(n)=ndμ(dn)F(d)f(n) = \sum\limits_{n|d} \mu(\frac dn)F(d)
证明方式类似。
其实在学到下文中的数论函数的狄利克雷卷积之后,莫比乌斯反演公式只需要几步即可证明。

然而实际上,通常情况下推导式子的时候使用莫比乌斯反演公式的话会非常麻烦,所以使用莫比乌斯函数的那个重要的性质足矣。

例:求 i=1nj=1m[gcd(i,j)=k]\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j) = k]
首先 i,ji,j 必为 kk 的倍数,故 kikj[gcd(i,j)=k]\sum\limits_{k|i}\sum\limits_{k|j} [\gcd(i,j)=k]
同样用到 gcd(agcd(a,b),bgcd(a,b))=1\gcd(\frac a{\gcd(a,b)},\frac b{\gcd(a,b)})=1 的性质,得 i=1nkj=1nk[gcd(i,j)=1]\sum\limits_{i=1}^{\lfloor\frac nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac nk\rfloor} [\gcd(i,j)=1]
dnμ(d)=[n=1]\sum\limits_{d|n} \mu(d) = [n=1] 代入 [gcd(i,j)=1][\gcd(i,j)=1],得 i=1nkj=1nkdgcd(i,j)μ(d)\sum\limits_{i=1}^{\lfloor\frac nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac nk\rfloor}\sum\limits_{d|\gcd(i,j)} \mu(d)
dd 提到最前面,得 d=1min(nk,mk)μ(d)ndkmdk\sum\limits_{d=1}^{\min(\lfloor\frac nk\rfloor,\lfloor\frac mk\rfloor)} \mu(d) \lfloor\frac n{dk}\rfloor\lfloor\frac m{dk}\rfloor
做到这一步,就可以使用数论分块的技巧求解了,复杂度是 O(nk+mk)O(\sqrt{\frac nk} + \sqrt{\frac mk})
你可能会问两个参数该如何数论分块,实际上,只需要每次令 r=min(nknkl,mkmkl)r = \min(\lfloor\frac{\lfloor\frac nk}{\lfloor\frac n{kl}\rfloor}\rfloor,\lfloor\frac{\lfloor\frac mk\rfloor}{\lfloor\frac m{kl}\rfloor}\rfloor) 即可。
此题即「『POI2007』Queries」。

如果你有在认真读,可能会注意到我把 nkd\lfloor\frac{\lfloor\frac nk\rfloor}d\rfloor 换成了 ndk\lfloor\frac n{dk}\rfloor(另外一个也是)。
证明:
nk=nk+c\frac nk = \lfloor\frac nk\rfloor + c,则 ndk=nkd+cd\frac n{dk} = \frac{\lfloor\frac nk\rfloor}d + \frac cd
注意到 nkdnkd+d1d\frac{\lfloor\frac nk\rfloor}d \le \lfloor\frac{\lfloor\frac nk\rfloor}d\rfloor + \frac{d-1}dcd<1d\frac cd < \frac1d
ndk=nkd+cd=nkd\lfloor\frac n{dk}\rfloor=\lfloor\frac{\lfloor\frac nk\rfloor}d + \frac cd\rfloor=\lfloor\frac{\lfloor\frac nk\rfloor}d\rfloor
证毕。

掌握套路之后,不妨再做点题。
例(「『SDOI2015』约数个数和」):求 i=1nj=1mσ0(ij)\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma_0(ij)
这里需要用到一个性质:

TeX parse error: Undefined control sequence \limit


这个性质在我当时做这道题的时候并不会证明,题解中也没有写。
现在来证一下。

对于一个 ,令 x=igcd(i,d),y=dgcd(i,d)x = \frac i{\gcd(i,d)},y = \frac d{\gcd(i,d)}
则显然易得
可得 ,又因为 gcd(x,y)=1\gcd(x,y)=1,故
于是可得
而对于任意的 都可以得到 ,并且与所有的 一一对应。
故原式得证。

然后接着来推导,这里就直接略去文字注释了:

之所以把后面的东西写成函数,是因为这两个式子只和 nd,md\lfloor\frac nd\rfloor,\lfloor\frac md\rfloor 有关。
易知 f(n)=i=1nnif(n) = \sum\limits_{i=1}^n \lfloor\frac ni\rfloor
这题数据范围比较小,所以说直接暴力预处理 O(nn)O(n \sqrt n) 是可以过的(视 n,mn,m 同阶)。

但是如果数据范围开到 10810^8(不考虑多组数据)?
不做预处理,直接在用到的时候暴力跑,因为 ff 函数只需要用到形如 ni\lfloor\frac ni\rfloor 处的值。
复杂度是 O(i=1n(i+ni))=O(1nnxdx)=O(n3/4)O(\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}(\sqrt i + \sqrt{\frac ni})) = O(\int_1^{\sqrt n}\sqrt{\frac nx}\text{d}x) = O(n^{3/4})
(实际上如果使用杜教筛求 μ\mu 前缀和的话,可以做到总共 O(n2/3)O(n^{2/3})

然而实际上 ff 函数是可以使用线性筛求出的。
注意到

于是 ff 其实就是 σ0\sigma_0 的前缀和。
线性筛出 σ0\sigma_0 即可。
具体方式是根据约数个数定理(σ0(n)=i=1m(ci+1)\sigma_0(n) = \prod\limits_{i=1}^m (c_i+1)cic_i 是前文提到的质因子分解的形式),线性筛时记录最小质因子的次数即可(因为只会被最小质因子筛到)。

在下文中还会再提到此题的 O(n2/3)O(n^{2/3}) 做法。

更多的习题还可以在我博客的莫比乌斯反演标签中找到。

狄利克雷卷积

定义两个数论函数 f,gf,g 的狄利克雷卷积 fgf*g 仍然是一个数论函数,且 (fg)(n)=dnf(d)g(nd)(f*g)(n) = \sum\limits_{d|n}f(d)g(\frac nd)
狄利克雷卷积满足交换律 fg=gff*g=g*f,结合律 (fg)h=f(gh)(f*g)*h=f*(g*h)
此处证明略去。

根据上文可得

上文中有提到莫比乌斯反演公式的狄利克雷卷积证明,即证明 f=μFf = \mu * F
证明:将 FF 代入后式,得
根据交换律与结合律得 ,故得证。

数论函数前缀和

我们常常会遇到数论函数的前缀和问题,尽管有时只是核心算法的一部分。
而很多时候,我们需要的是所有 ni\lfloor\frac ni\rfloor 处的前缀和值。
然后呢,有一种常用的算法,可以用来对一些常见的数论函数解决这个问题。

杜教筛

对于积性函数 f,g,h=fgf,g,h = f*g,考虑 i=1nh(i)\sum\limits_{i=1}^n h(i)

TeX parse error: Undefined control sequence \limtis

S(n)=i=1nf(i)S(n) = \sum\limits_{i=1}^n f(i),则原式即 d=1ng(d)S(nd)\sum\limits_{d=1}^ng(d)S(\lfloor\frac nd\rfloor)
从和式中提出 d=1d=1 一项,得 i=1nh(i)=g(1)S(n)+d=2ng(d)S(nd)\sum\limits_{i=1}^n h(i) = g(1)S(n) + \sum\limits_{d=2}^n g(d)S(\lfloor\frac nd\rfloor)
注意到 g(1)=1g(1)=1,故 S(n)=i=1nh(i)d=2ng(d)S(nd)S(n) = \sum\limits_{i=1}^n h(i) - \sum\limits_{d=2}^n g(d)S(\lfloor\frac nd\rfloor)

若能较快地求出 g,hg,h 的前缀和,即可递归地求 S(n)S(n)
记忆化之后,实际上就是对于所有 ni\lfloor\frac ni\rfloor 花费了 O(ni)O(\sqrt{\frac ni}\rfloor) 的复杂度。
总复杂度即 undefined。
若预处理 nc(c>12)n^c\,(c > \frac12) 以内的值,则复杂度变为 O(nc+n1c2)O(n^c + n^{1-\frac c2})
c=23c = \frac23 时两项平均达到最优值 O(n2/3)O(n^{2/3})

arknights