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

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

前置知识

求和符号∑\sum

∑if(i)+g(i)=∑if(i)+∑ig(i)∑i∑jf(i)g(j)=∑j∑if(i)g(j)=(∑if(i))∗(∑jg(j))∑ik∗f(i)=k∗∑if(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=1n∑d∣if(d)=∑d=1n∑i=1⌊nd⌋f(d)=∑d=1n⌊nd⌋f(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)=∑d∣xf(d)g(xd)h(x) = \sum_{d|x}f (d)g (\frac{x}{d})

  3. 常见积性函数：(令 n=p1a1p2a2⋯pkakn = 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)=∑d∣n1\mathrm{d}(n) = \sum_{d|n} 1
    • 约数和函数: σ(n)=∑d∣nd\sigma(n) = \sum_{d|n} d
    • 刘维尔函数: λ(n)=(−1)k\lambda(n) = (-1)^k

线性筛

我们还是令 x=p1a1∗p2a2...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×p−1p\varphi(p^a) =p^a\times \frac{p-1}{p}

    此处的证明：

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

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

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

    所以φ(pa)=pa−pa−1=pa×p−1p\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. 定义： (f∗g)(n)=∑d∣nf(d)g(nd)(f * g)(n) = \sum_{d|n} f(d) g(\frac{n}{d})

  2. 性质：

    交换律：f∗g=g∗ff*g=g*f

    结合律：(f∗g)∗h=f∗(g∗h)(f*g)*h=f*(g*h)

    分配律：f∗(g+h)=f∗g+f∗hf*(g+h)=f*g+f*h

    单位元：f∗ϵ=ϵ∗f=ff*\epsilon=\epsilon * f=f

  3. 常见关系：

    • μ∗1=ϵ\mu * 1 = \epsilon(即[n=1]=∑d∣nμ(d)[n=1]=\sum_{d|n}\mu(d))
    • Id=φ∗1⇒φ=μ∗Id\mathrm{Id} = \varphi * 1 \Rightarrow \varphi = \mu * \mathrm{Id}(即n=∑d∣nφ(d)n=\sum_{d|n}\varphi(d)，φ(n)=∑d∣nndμ(d)\varphi(n)=\sum_{d|n}\frac{n}{d}\mu(d))
    • d=1∗1⇒1=μ∗d\mathrm{d} = 1 * 1 \Rightarrow 1 = \mu * \mathrm{d}
    • σ=Id∗1⇒Id=μ∗σ\sigma = \mathrm{Id} * 1 \Rightarrow \mathrm{Id} = \mu * \sigma

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

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

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

    • σ(ij)=∑x∣i∑y∣j[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=1⌊n⌋μ(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)=n∗∏i(1−1pi)\varphi(n)=n*\prod\limits_{i}(1-\frac{1}{p_i}) （pip_i为nn的质因子）

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

    由上面线性筛的部分我们知道φ(pa)=pa×p−1p\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})

    所以φ(n)=p1a1p2a2...pkak×∏i=1k(1−1pi)=n∗∏i=1k(1−1pi)\varphi(n) = p_1^{a_1}p_2^{a_2}...p_k^{a_k}\times\prod\limits_{i=1}^{k}(1-\frac{1}{p_i}) = n*\prod\limits_{i=1}^{k}(1-\frac{1}{p_i})

  2. 性质：n=∑d∣nφ(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. 运用（常见套路）：

    ∑i∑jgcd(i,j)=∑i∑j∑d∣gcd(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]=∑d∣nμ(d)[n=1]=\sum_{d|n}\mu(d)

    证明：

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

    2. n≠1n\ne1时

      ∑d∣nμ(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)i1k−i=(1−1)n=0\sum_{i=0}^kC_k^i(-1)^i1^{k-i}=(1-1)^n=0)

  3. 运用（常见套路）：

    ∑i∑j[gcd(i,j)==1]=∑i∑j∑d∣gcd(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)=∑d∣ng(d)⇒g(n)=∑d∣nμ(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=1∗g∗μ=ϵ∗g=g \begin{aligned} \because \mu*1&=\epsilon\\ \therefore \mu*f=1*g*\mu&=\epsilon*g=g \end{aligned}
  3. 扩展：f(n)=∑d∣ng(d)⇒g(n)=∑d∣nμ(nd)f(d)f(n)=∑n∣dg(d)⇒g(n)=∑n∣dμ(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=1n⌊ni⌋\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显然等于⌊n⌊nl⌋⌋\lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor}\rfloor

即i∈[l,⌊n⌊nl⌋⌋]i\in[l, \lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor}\rfloor]时，答案都为⌊nl⌋\lfloor \frac{n}{l}\rfloor

那么把这部分答案O(1)O(1)算出来，再令i=⌊n⌊nl⌋⌋+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

n≤109n\le 10^9

Solution

首先构造h=f∗gh=f*g（gg是一个任意的数论函数），设HH为hh的前缀和函数

开始疯狂推式子

H(n)=∑i=1n∑d∣if(d)g(⌊id⌋)=∑i=1n∑d∣ig(d)f(⌊id⌋)=∑d=1ng(d)∑d∣if(⌊id⌋)=∑d=1ng(d)∑i=1⌊nd⌋f(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

比如:

  • 筛μ\mu：g=1g=1，利用ϵ=1∗μ\epsilon=1*\mu，此时F(n)=1−∑i=2nF(⌊ni⌋)F(n)=1-\sum_{i=2}^{n}F(\lfloor \frac{n}{i}\rfloor)

  • 筛φ\varphi：g=1g=1，利用Id=1∗φ\mathrm{Id}=1 * \varphi，此时F(n)=n(n+1)2−∑i=2nF(⌊ni⌋)F(n)=\frac{n(n+1)}{2}-\sum_{i=2}^{n}F(\lfloor \frac{n}{i}\rfloor)

代码及例题

「BZOJ1101」ZAP-Queries

「Luogu P3768」简单的数学题