数论函数这一块一直迷迷糊糊似懂非懂,最近花了点时间补了补基础知识

写这篇博客花了整整一下午的时间,希望哪天不记得的时候再翻这篇博客会有收获吧

前置知识

求和符号\sum

if(i)+g(i)=if(i)+ig(i)ijf(i)g(j)=jif(i)g(j)=(if(i))(jg(j))ikf(i)=kif(i) \begin{aligned} \sum_{i}f(i)+g(i)&=\sum_{i}f(i)+\sum_{i}g(i) \\ \sum_{i}\sum_{j}f(i)g(j)&=\sum_{j}\sum_{i}f(i)g(j)=(\sum_{i}f(i))*(\sum_{j}g(j)) \\ \sum_{i}k*f(i)&=k*\sum_{i}f(i) \end{aligned}

枚举约数转化为枚举倍数

i=1ndif(d)=d=1ni=1ndf(d)=d=1nndf(d) \sum_{i=1}^{n}\sum_{d|i}f(d)=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(d)=\sum_{d=1}^{n}\lfloor \frac{n}{d}\rfloor f(d)

数论函数

积性函数

  1. 定义(最基本性质): gcd(a,b)=1\forall gcd(a, b) = 1,满足 f(ab)=f(a)f(b)f (ab) = f (a) f (b) 的函数。若去掉互质的条件仍满足,则为完全积性函数

  2. 性质:若 f(x),g(x)f (x), g (x)是积性函数,那么以下函数皆为积性函数

    • h(x)=f(xp)h(x) = f (x^p )
    • h(x)=fp(x)h(x) = f^p (x)
    • h(x)=f(x)g(x)h(x) = f (x)g (x)
    • h(x)=dxf(d)g(xd)h(x) = \sum_{d|x}f (d)g (\frac{x}{d})
  3. 常见积性函数:(令 n=p1a1p2a2pkakn = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k})

    • 单位元: ϵ(n)=[n=1]\epsilon(n) = [n = 1]
    • 恒等函数:1(n)=11(n) = 1
    • 单位函数:Id(n)=n\mathrm{Id}(n) = n
    • 莫比乌斯函数: μ(n)=[max(a1,a2,...,ak)1](1)k\mu(n) = [\max(a_1, a_2, ..., a_k) \leq 1] (-1)^k
    • 欧拉函数:φ(n)=i=1n[(i,n)=1]\varphi(n)=\sum_{i=1}^n[(i,n)=1]
    • 约数个数函数: d(n)=dn1\mathrm{d}(n) = \sum_{d|n} 1
    • 约数和函数: σ(n)=dnd\sigma(n) = \sum_{d|n} d
    • 刘维尔函数: λ(n)=(1)k\lambda(n) = (-1)^k

线性筛

我们还是令 x=p1a1p2a2...pkakx = p_1^{a_1} *p_2^{a_2} ... p_k^{a_k} , 则根据积性函数的性质有 f(x)=f(p1a1)×f(xp1a1)f(x) = f(p_1^{a_1} ) \times f(\frac{x}{p_1^{a_1}}) 这个p1p_1即为xx的最小质因子

因此,对于任意的积性函数,若 f(pa)f (p^a ) (pp为质数) 可以快速求出,那么就可以线性筛.

例如:

  • φ(pa)=pa×p1p\varphi(p^a) =p^a\times \frac{p-1}{p}

    此处的证明:

    φ(pa)\varphi(p^a)表示小于pap^a的数中与pap^a互质的数

    它等于pap^a减去与pap^a不互质的数

    显然,与pap^a不互质的数一共有pa1p^{a-1}个,它们分别是1×p,2×p,3×p,...pa1×p1\times p,2\times p, 3\times p, ... p^{a-1}\times p

    所以φ(pa)=papa1=pa×p1p\varphi(p^a)=p^a-p^{a-1}=p^a\times\frac{p-1}{p}

  • μ(pa)=1[a=1]\mu(p^a) =-1[a=1]

  • d(pa)=a+1\mathrm{d}(p^a)=a+1

  • σ(pa)=i=0api\sigma(p^a)=\sum_{i=0}^ap^i

具体φ\varphi的线性筛

狄利克雷卷积

  1. 定义: (fg)(n)=dnf(d)g(nd)(f * g)(n) = \sum_{d|n} f(d) g(\frac{n}{d})

  2. 性质:

    交换律:fg=gff*g=g*f

    结合律:(fg)h=f(gh)(f*g)*h=f*(g*h)

    分配律:f(g+h)=fg+fhf*(g+h)=f*g+f*h

    单位元:fϵ=ϵf=ff*\epsilon=\epsilon * f=f

  3. 常见关系:

    • μ1=ϵ\mu * 1 = \epsilon(即[n=1]=dnμ(d)[n=1]=\sum_{d|n}\mu(d))
    • Id=φ1φ=μId\mathrm{Id} = \varphi * 1 \Rightarrow \varphi = \mu * \mathrm{Id}(即n=dnφ(d)n=\sum_{d|n}\varphi(d)φ(n)=dnndμ(d)\varphi(n)=\sum_{d|n}\frac{n}{d}\mu(d))
    • d=111=μd\mathrm{d} = 1 * 1 \Rightarrow 1 = \mu * \mathrm{d}
    • σ=Id1Id=μσ\sigma = \mathrm{Id} * 1 \Rightarrow \mathrm{Id} = \mu * \sigma

    下面三个式子没那么容易一眼看出来,但是仔细推一推也是比较好理解的

    • σ=φd\sigma = \varphi * \mathrm{d}

    • d(ij)=xiyj[gcd(x,y)=1]\mathrm{d}(ij) = \sum_{x | i} \sum_{y | j} [\mathrm{gcd}(x, y) = 1]

    • σ(ij)=xiyj[gcd(ix,y)=1]xy\sigma(ij) = \sum_{x | i} \sum_{y | j} [\mathrm{gcd}(\frac{i}{x}, y) = 1]xy

      2018.12.18 Update

      还是感性证明一下这个式子吧

      首先,这个式子大致的意思是选ii的一个约数和jj的一个约数相乘

      虽然得到的数一定是ijij的约数,但是显然这样会算重

      感性理解一下[gcd(ix,y)=1][gcd(\frac{i}{x},y)=1]这个条件实际上就是要满足对于任意一个质因子pp,若在yy中出现的话,xx中就必须要取完

      换句话说,如果pp在最后的约数中的次数小于在ii中的次数的话,那它只能在xx中出现,yy中不能出现;而如果大于在ii中的次数的话,那么在xx中的次数就必须等于在ii中的次数

      可以发现,这样做的话,相当于是pp这个质因子按照先从ii再从jj的顺序进行选取,这样就保证了不会算重

    • i=1nμ2(i)=i=1nμ(i)ni2\sum_{i=1}^n \mu^2(i) = \sum_{i=1}^{\lfloor\sqrt{n}\rfloor} \mu(i) \lfloor \frac{n}{i^2} \rfloor(最后这个暂时没看太懂。。。)

欧拉函数φ\varphi

  1. 定义:φ(n)=i=1n[(i,n)=1]\varphi(n)=\sum_{i=1}^n[(i,n)=1]

    另外一种计算方法:φ(n)=ni(11pi)\varphi(n)=n*\prod\limits_{i}(1-\frac{1}{p_i})pip_inn的质因子)

    19.3.2 UPD 关于这个计算方法的证明

    由上面线性筛的部分我们知道φ(pa)=pa×p1p\varphi(p^a)=p^a\times \frac{p-1}{p},且φ(n)=φ(p1a1)×φ(p2a2)×...×φ(pkak)\varphi(n) = \varphi(p_1^{a_1})\times \varphi(p_2^{a_2})\times...\times\varphi(p_k^{a_k})

    所以

  2. 性质:n=dnφ(d)n=\sum_{d|n}\varphi(d)

    感性证明:

    考虑所有分母为nn,分子为1,2,..,n1,2,..,n的这nn个分数

    将分数约分后,分子分母是互质的,且分母是整除nn的,且分数互不相同

    对于每个不同的分母xx,一定会有φ(x)\varphi(x)个分子与其对应,于是得证

    例如n=6n=6时:

    16,26,36,46,56,66 \frac{1}{6},\frac{2}{6},\frac{3}{6},\frac{4}{6},\frac{5}{6},\frac{6}{6}

    约分后是

    16,13,12,23,56,11 \frac{1}{6},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{5}{6},\frac{1}{1}

    其中φ(1)=1,φ(2)=1,φ(3)=2,φ(6)=2\varphi(1)=1, \varphi(2)=1, \varphi(3)=2,\varphi(6)=2

  3. 运用(常见套路):

    ijgcd(i,j)=ijdgcd(i,j)φ(d) \sum_{i}\sum_{j}gcd(i,j)=\sum_{i}\sum_{j}\sum_{d|gcd(i,j)}\varphi(d)

莫比乌斯函数μ\mu

  1. 定义:μ(n)=[max(a1,a2,...,ak)1](1)k\mu(n) = [\max(a_1, a_2, ..., a_k) \leq 1] (-1)^k

  2. 性质:[n=1]=dnμ(d)[n=1]=\sum_{d|n}\mu(d)

    证明:

    1. 显然n=1n=1dnμ(d)=1\sum_{d|n}\mu(d)=1

    2. n1n\ne1

      dnμ(d)=μ(1)+μ(p1)+μ(p2)+...+μ(p1p2)+...+μ(p1p2...pk)=i=0kCki(1)i=0 \begin{aligned} \sum_{d|n}\mu(d)&=\mu(1)+\mu(p_1)+\mu(p_2)+...+\mu(p_1p_2)+...+\mu(p_1p_2...p_k)\\ &=\sum_{i=0}^kC_k^i(-1)^i\\ &=0 \end{aligned}

      最后一步是由二项式定理得到

      (i=0kCki(1)i1ki=(11)n=0\sum_{i=0}^kC_k^i(-1)^i1^{k-i}=(1-1)^n=0)

  3. 运用(常见套路):

    ij[gcd(i,j)==1]=ijdgcd(i,j)μ(d) \sum_{i}\sum_{j}[gcd(i,j)==1]=\sum_{i}\sum_{j}\sum_{d|gcd(i,j)}\mu(d)

莫比乌斯反演

其实主要内容上面都已经证明过了

  1. 定义:f(n)=dng(d)g(n)=dnμ(d)f(nd)f(n)=\sum_{d|n}g(d) \Rightarrow g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})

  2. 从卷积角度理解:

    μ1=ϵμf=1gμ=ϵg=g \begin{aligned} \because \mu*1&=\epsilon\\ \therefore \mu*f=1*g*\mu&=\epsilon*g=g \end{aligned}
  3. 扩展:f(n)=dng(d)g(n)=dnμ(nd)f(d)f(n)=ndg(d)g(n)=ndμ(dn)f(d) \begin{aligned} f(n) = \sum_{d|n} g(d) &\Rightarrow g(n) = \sum_{d|n} \mu(\frac{n}{d}) f(d) \\ f(n) = \sum_{n|d} g(d) &\Rightarrow g(n) = \sum_{n|d} \mu(\frac{d}{n}) f(d) \end{aligned}

整除分块

容易发现,当 i=1...ni = 1 ... n 时,ni\lfloor \frac{n}{i} \rfloor 只有 O(n)O(\sqrt{n}) 种不同的取值

这个性质经常被用来优化复杂度

具体操作是,如果当i[l,r]i\in[l,r]时的答案相同,那么当i=li=l时一次性算出这段区间的答案,然后令i=r+1i=r+1,不断重复操作

举个最简单的例子:

i=1nni\sum_{i=1}^n \lfloor \frac{n}{i}\rfloor

注意到,当i=li=l时,贡献为nl\lfloor \frac{n}{l}\rfloor,而贡献为nl\lfloor \frac{n}{l}\rfloor的最大的ii显然等于nnl\lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor}\rfloor

i[l,nnl]i\in[l, \lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor}\rfloor]时,答案都为nl\lfloor \frac{n}{l}\rfloor

那么把这部分答案O(1)O(1)算出来,再令i=nnl+1i=\lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor}\rfloor+1,重复此过程即可

因为ni\lfloor \frac{n}{i}\rfloor的取值是O(n)O(\sqrt n)的,所以复杂度时O(n)O(\sqrt n)

杜教筛

杜教筛主要是用来快速求一些数论函数的前缀和

上面内容都理解了的话,杜教筛其实是非常简单的

Description

求某个数论函数ff的前缀和FF

n109n\le 10^9

Solution

首先构造h=fgh=f*ggg是一个任意的数论函数),设HHhh的前缀和函数

开始疯狂推式子

H(n)=i=1ndif(d)g(id)=i=1ndig(d)f(id)=d=1ng(d)dif(id)=d=1ng(d)i=1ndf(i)=d=1ng(d)F(nd) \begin{aligned} H(n)&=\sum_{i=1}^n\sum_{d|i}f(d)g(\lfloor \frac{i}{d}\rfloor)\\ &=\sum_{i=1}^n\sum_{d|i}g(d)f(\lfloor \frac{i}{d}\rfloor)\\ &=\sum_{d=1}^ng(d)\sum_{d|i}f(\lfloor \frac{i}{d}\rfloor)\\ &=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(i)\\ &=\sum_{d=1}^ng(d)F(\lfloor \frac{n}{d}\rfloor)\\ \end{aligned} F(n)g(1)=H(n)i=2ng(i)F(ni) \Rightarrow F(n)g(1)=H(n)-\sum_{i=2}^{n}g(i)F(\lfloor \frac{n}{i}\rfloor)

稍微解释一下上面式子怎么推的:

第一步:积性函数的交换律

第二步:把dd提出来,枚举因数转化为枚举倍数

第三步:把枚举ii转化为直接枚举id\lfloor \frac{i}{d}\rfloor

第四步:根据FF的定义代入

第五步:令d=1d=1,代入

通过观察最后这个式子可以发现,后面部分可以整除分块,求FF的话可以小范围线性筛预处理(大约10710^7的表),大范围递归记忆化

那么只要H(n)H(n)能快速计算,就能做到低于线性(大约O(n23)O(n^{\frac{2}{3}}))的复杂度了(复杂度并不会证)

具体的,对于求不同的ff,往往选择使得HH更快更好求的函数hh

比如:

  • μ\mug=1g=1,利用ϵ=1μ\epsilon=1*\mu,此时F(n)=1i=2nF(ni)F(n)=1-\sum_{i=2}^{n}F(\lfloor \frac{n}{i}\rfloor)

  • φ\varphig=1g=1,利用Id=1φ\mathrm{Id}=1 * \varphi,此时F(n)=n(n+1)2i=2nF(ni)F(n)=\frac{n(n+1)}{2}-\sum_{i=2}^{n}F(\lfloor \frac{n}{i}\rfloor)

代码及例题

「BZOJ1101」ZAP-Queries

「Luogu P3768」简单的数学题