积性函数,莫比乌斯反演,杜教筛

我来填坑啦

积性函数

若对于定义在正整数集上的f(x)f(xy)=f(x)f(y)gcd(x,y)==1成立时,则称f(x)为积性函数,若满足f(xy)=f(x)f(y)但不要求gcd(x,y)==1则称f(x)为完全积性。

性质:积性函数的卷积还是积性函数

积性函数通常可以由线性筛求得。

常见积性函数

(1). \varphi(n) 欧拉函数 Notice : \sum_{i=1}^n{i\times [(n,i) == 1]} = \frac{\varphi(n)\times n + [n == 1]}{2}
(2). \sigma_k(n) 表示n的约数的k次幂和
(3). \tau(n) = \sigma_0(n) 表示n的约数的个数
(4). \mu(n) 莫比乌斯函数 Notice : \sum_{d|n} {\mu(d) } = [n == 1]
(5). \epsilon(n) = [n==1] 狄利克雷卷积的乘法单位元 完全积性
(6). id(n) = n 单位函数 完全积性
(7). I(n) = 1 恒等函数 完全积性
做题的时候不知道是不是积性函数可以打个表大胆猜测一下

莫比乌斯函数的性质

对于任意正整数n有:\sum_{d|n} {\mu(d) } = [n == 1]

\mu(n)=\begin{cases} 1 & n=1 \\(-1)^m & \prod_{i=1}^mk_i=1 \\0 & otherwise(k_i>1)\end{cases}

\mu常作为容斥的系数来考虑。

狄利克雷卷积

数论函数fg的狄利克雷卷积定义为(f*g)(n)=\sum_{d|n}f(d)\times g(\frac{n}{d})
狄利克雷卷积满足交换律、结合律,对加法满足分配律,存在单位元函数\epsilon(n)=[n==1]使得f*\epsilon=f=\epsilon*f
例如:\mu*id=\varphi \mu*i=\epsilon\varphi*i=id

一些技巧

\sum_{i=1}^n{\lfloor \frac{n}{i} \rfloor} 因为 \lfloor \frac{n}{i} \rfloor有很多相同的值,因此可以数论分块,可以证明最多分成2\sqrt n块。

莫比乌斯反演

公式:f(n)=\sum_{d|n}g(d) \to g(n) = \sum_{d|n} \mu(d)f(\frac{n}{d})
证明:f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k)=\sum_{k|n}f(k)\sum_{d|\frac{n}{k}}\mu(d)=f(n)
形式二:g(n)=\sum_{n|d}f(d) \to f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)
形式二一般比较常用

一些傻逼的例子&莫比乌斯反演的应用

所有式子默认n \leq m ,若不满足则交换。

对于一些函数f(n),如果我们很难直接求出他们的值,而容易求出他们的倍数和或约数和g(n),那么我们可以通过莫比乌斯反演来求f(n)

1D Gcd Sum : \sum_{i=1}^ngcd(n,i)=\sum_{i=1}^n\sum_{d|gcd(n,i)}\varphi(d)=\sum_{d|n}\lfloor \frac{n}{i} \rfloor \varphi(d)

2D Gcd Sum : \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\varphi(d)=\sum_{d|n}\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor \varphi(d)

2D Prime Sum : \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==1]=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\mu(d)=\sum_{d=1}^n\mu(d)\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor

1D Prime Sum : \sum_{1\leq i \leq n,gcd(i,n)=1}i=\sum_{i=1}^n{i[gcd(n,i)==1]}=\frac{n}{2}(\mu \times id + \mu \times i)=\frac{n\times \varphi(n) + [n==1]}{2}

1D Lcm Sum :\sum_{i=1}^nlcm(i,n)=n\sum_{i=1}^n\frac{i}{gcd(n,i)}=n\sum_{d|n}\sum_{i=1}^{\frac{n}{d} }{i[gcd(i,\frac{n}{d})==1]}=n\sum_{d|n}g(\frac{n}{d})
因为有g(n)=\frac{n\times \varphi(n)+[n==1]}{2} 因此 \sum_{i=1}^nlcm(i,n)=n\sum_{d|n}\frac{\varphi(d)\times d}{2}

2D Lcm Sum :ans=\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)=\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)} 我们选择枚举d=gcd(i,j)且设F(x,y)=\sum_{1\leq i \leq x,1\leq j \leq y,gcd(i,j)=1}i\times j,则有ans=\sum_{d=1}{n}\frac{d^2F(\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor)}{d}=\sum_{i=1}^{n}{d\times F(\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor)},继续定义Sum(x,y)=\sum_{i=1}^{x}\sum_{j=1}^{y}i\times j=\frac{x(x+1)}{2}\frac{y(y+1)}{2}那么我们可以得出F(x,y)=\sum_{i=1}^{min(x,y)}i^2\times \mu(i) \times Sum(\lfloor \frac{x}{i} \rfloor, \lfloor \frac{y}{i} \rfloor)时间复杂度O(n),此式还可以进一步优化但我实在写不动了,坑了

2D Gcd = k Sum : \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==k] 我们设f(k)gcd(i,j)=k的个数,设g(k)k|gcd(i,j)的个数,则有关系g(k)=\sum_{x=1}^{\lfloor \frac{n}{k} \rfloor}{f(k\times x)},易得g(k)=\lfloor \frac{n}{k} \rfloor \lfloor \frac{m}{k} \rfloor,然后直接上莫比乌斯反演得f(k)=\sum_{x=1}^{\lfloor \frac{n}{k} \rfloor}\mu(x)g(x\times k),显然f(k)即为所求,我们采用数论分块的方式就可以降到O(\sqrt n + \sqrt m)

莫比乌斯反演应该还有些操作,懒得写了,坑了

杜教筛

步入正题

首先掏出tls的blog
杜教筛的学习要点by冯爷:给一个已知积性函数配一个积性函数卷积后的积性函数的前缀和很好算。
杜教筛的学习要点byzbh:要会算时间复杂度。zbh爷表示非常bs博客说成高阶无穷小量而不证复杂度的,强行积分证复杂度QAQ
常见的积性函数可以自觉回到上面去看。

给出杜教筛的一般形式

比如说要求一个积性函数f(i)的前缀和F(i),即F(i)=\sum_{i=1}^nf(i),我们就可以找个积性函数g(i),把gf做一个卷积(g*f)(i)=\sum_{d|i}g(d)f(\frac{i}{d}),再求一下卷积的前缀和\sum_{i=1}^n(g*f)(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d}),把d提出来操作一番\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d}) = \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)因此我们可以得到g(1)F(n)=\sum_{i=1}^ng(i)f(\lfloor \frac{n}{i} \rfloor)-\sum_{i=2}^ng(i)F(\lfloor \frac{n}{i} \rfloor)我们发现等号右边的前面的这个玩意是一个狄利克雷卷积,因此有g(1)F(n)=\sum_{i=1}^n(g*f)(i)-\sum_{i=2}^ng(i)F(\lfloor \frac{n}{i} \rfloor)
如果狄利克雷卷积的前缀和非常好算的话,那么我们就可以对后面的东西进行数论分块,然后递归计算。记得要记忆化搜索,其实map也能跑得飞快(雾

按照jiry_2说的应该有两种形式,转自jiry_2’s blog
F(n)=\sum_{i=1}^n(f*g)(i)g为完全积性函数
则有F(n)=\sum_{i=1}^n((f*1)*g)(i)-\sum_{i=1}^ng(i)F(\lfloor \frac{n}{i} \rfloor)
F(n)=\sum_{i=1}^n(f*g)(i)
则有F(n)=\sum_{i=1}^ng(i)\sum_{ij\leq n}(f*1)(j)-\sum_{i=1}^nF(\lfloor \frac{n}{i} \rfloor)

杜教筛例题1

Ans = \sum_{i=1}^n\varphi(i) 其中 1\leq n \leq 10^{11}

这个公式也可以看成n-\sum_{1\leq i \leq n,i \neq n}\varphi(i) 定义\phi(n)=\sum_{i=1}^n\varphi(n),于是\phi(n)=\sum_{i=1}^n\varphi(i)=\sum_{i=1}^ni-\sum_{d|i,d\neq i}\varphi(d)=\frac{n\times (n+1)}{2}-\sum_{i=1}^n\sum_{d|i,d\neq i}\varphi(d)=\frac{n\times (n+1)}{2}-\sum_{\frac{i}{d}}^n\sum_{d=1}^{\frac{n}{\frac{i}{d}}}\varphi(d)
=\frac{n\times (n+1)}{2}-\sum_{i=2}^n\sum_{d=1}^{\lfloor \frac{n}{i} \rfloor}\varphi(d)=\frac{n\times (n+1)}{2}-\sum_{i=2}^n-\phi(\lfloor \frac{n}{i} \rfloor )

考虑计算出\lfloor \frac{n}{i} \rfloor\phi(\lfloor \frac{n}{i} \rfloor)值,就可以计算出\phi(n),现在来算算时间复杂度。设T(n)=O(\sqrt n) + \sum_{i=1}^{\sqrt n}T(i)+T(\frac{n}{i})+\sqrt n,运用微积分的知识简单算算可以得到T(n)=O(\sum_{i=1}^{\sqrt n}({\frac{\sqrt n}{i}+\sqrt i}) + \sqrt n)=O(2\sqrt {\sqrt n} +\sqrt n) = O(2n^{\frac{3}{4}}),但是呢因为\phi(n)本身是一类积性函数的前缀和,可以用筛法解决一部分,假设处理到\phi(k),则复杂度变为T(n)=\sum_{i=1}^{\frac{n}{k}}\sqrt {\frac{n}{i}} = \frac{n}{\sqrt k} 使\frac{n}{\sqrt k}=n^{\frac{3}{4}}解得k=n^{\frac{2}{3}}时,复杂度可取到最小为n^{\frac{2}{3}}

杜教筛例题2

Ans = \sum_{i=1}^n\mu(i) 其中 1\leq n \leq 10^{11}
M(n)\sum_{i=1}^n\mu(i),我们套用上面杜教筛的一般模板得到g(1)M(n)=\sum_{i=1}^n(g * \mu)(i)-\sum_{i=2}^ng(i)M(\lfloor \frac{n}{i} \rfloor),同时我们知道\mu * i=\epsilon\sum_{d|i}\mu(d)=[i==1]\epsilon的前缀和是1,因此g(x)=1,得到M(n)=1-\sum_{i=2}^n{M(\lfloor \frac{n}{i} \rfloor)}

写在最后,不要因为知道杜教筛和线性筛就tm老想筛,有时候暴力的埃氏筛也不错QAQ

一些题目

莫比乌斯函数之和
利用1 * \mu = \epsilon
欧拉函数之和
利用1 * \varphi = id
BZOJ 3944 Sum
貌似就是上面两道题的总和,注意要一块算不然会T
51nod 最小公倍数之和3
\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)
=\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}
=\sum_{d=1}^{n}\frac{\sum_{i=1}^n\sum_{j=1}^mij[gcd(i,j)==d]}{d}
=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}ij[gcd(i,j)==1]
=\sum_{d=1}^{n}d(2(\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j=1}^ij[gcd(i,j)==1])-1)
观察到\sum_{j=1}^ij[gcd(i,j)==1]实际上就是\frac{i\varphi(i)+[n==1]}{2}
=\sum_{d=1}^nd(2(\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i \frac{i\varphi(i)+[i==1]}{2}-1)
=\sum_{d=1}^nd(\sum_{i=1}^{\frac{n}{d}}i^2\varphi(i)+[i==1])-1
=\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}i^2\varphi(i)
接下来我们需要求i^2\varphi的前缀和,丢两个id卷进去
=\sum_{d=1}^n\sum_{d|i}d^2\varphi(d)(\frac{i}{d})^2
=\sum_{k=1}^nk^2\sum_{d=1}^{\lfloor \frac{n}{d} \rfloor} d^2 \varphi(d)
所以有\sum_{i=1}^ni^2\varphi(i)=(\frac{n(n+1)}{2})^2 - \sum_{k=1}^{n}k^2\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i^2\varphi(i)