前置知识
狄利克雷卷积:\(f * g = \sum_{d|n}f(d)g(\frac{n}{d})\)。
积性函数,线性筛。
数论分块。
单位函数:\(\varepsilon(n)=[n=1]\)。(积性函数)
常数函数:\(1(n)=1\)。(积性函数)
莫比乌斯函数
引理1: \(f(n)\) 是积性函数等价于 \(g(n)=\sum_{d|n}f(d)\) 是积性函数。
证明:
显然,\(g=f * 1\),所以 \(f(n)\) 是积性函数可以推出 \(g(n)\) 是积性函数。
若 \(g(n)\) 是积性函数,归纳法。
首先,\(g(1)=f(1)\),因为 \(g(1)=g(1)g(1)\),所以 \(f(1)=g(1)=1\)。
假设对于所有小于 \(n\) 的值,\(f(n)\) 都是积性函数。
不妨设 \(n=ab,\gcd(a,b)=1\),则有:
\[\begin{aligned} g(n) &= g(ab)\\ &= \sum_{d|ab}f(d)\\ &= \sum_{d_1|a}\sum_{d_2|b}f(d_1d_2)\\ &= \sum_{d_1|a}\sum_{d_2|b}f(d_1)f(d_2)-f(a)f(b)+f(ab) \end{aligned} \]又因为:
\[\begin{aligned} g(n) &= g(a)g(b)\\ &= \sum_{d_1|a}f(d_1)\sum_{d_2|b}f(d_2)\\ &= \sum_{d_1|a}\sum_{d_2|b}f(d_1)f(d_2) \end{aligned} \]两式联立,得 \(-f(a)f(b)+f(ab)=0\),即 \(f(n)=f(ab)=f(a)f(b)\),得证。
定义: 满足 \(\sum_{d|n}\mu(d)=\varepsilon(n)\) 的函数 \(\mu\) 称作莫比乌斯函数。
性质1: 莫比乌斯函数是积性函数。
证明:
由于 \(\varepsilon(n)\) 是积性函数,根据引理1可知,\(\mu(n)\) 也是积性函数。
性质2: \(p\) 为质数,则:
\[\mu(p^k)= \begin{cases} 1&k=0\\ -1&k=1\\ 0&k>1 \end{cases} \]说明:
代入定义的式子得到 \(\sum_{i=0}^k\mu(p^i)=\varepsilon(p^k)\),推一下就可以得到。
性质3: 设 \(n\) 质因数分解后有 \(k\) 个不同的质因数,则:
\[\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{有平方因子}\\ (-1)^k& \text{Otherwise.} \end{cases} \]说明:
根据 \(\mu(p^k)\) 以及它是积性函数可得。
莫比乌斯反演
反演公式1:
\[g(n)=\sum_{d|n}f(d)\iff f(n)=\sum_{d|n}\mu(\frac{n}{d})g(d) \]反演公式2:
\[g(n)=\sum_{n|d}f(d)\iff f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d) \]证明:
这里只证明公式 1。
考虑狄利克雷卷积。
首先,狄利克雷卷积满足交换律,结合律。
则 \(g = f * 1\),所以:
\[\begin{aligned} f(n)&=\sum_{d|n}\mu(\frac{n}{d})g(d)\\ &=\mu * g\\ &=\mu * (f * 1)\\ &=(\mu * 1) * f\\ &=\varepsilon * f\\ &=f \end{aligned} \]得证。
证明2:
\[\begin{aligned} \sum_{d|n}\mu(\frac{n}{d})g(d) &= \sum_{d|n}\mu(\frac{n}{d})\sum_{d'|d}f(d')\\ &= \sum_{d|n}f(d)\sum_{d' = d j|n}\mu(\frac{n}{d'})\\ &= \sum_{d|n}f(d)\sum_{j|\frac{n}{d}}\mu(\frac{n}{dj})\\ &= \sum_{d|n}f(d)\sum_{j|\frac{n}{d}}\mu(j)\\ &= \sum_{d|n}f(d)\varepsilon(\frac{n}{d})\\ &= f(n) \end{aligned} \]得证。
应用
题目1: 求 \(\sum_{i=x}^n\sum_{j=y}^m[\gcd(i,j)=k]\)。(P2522 [HAOI2011] Problem b,P3455 [POI2007] ZAP-Queries)
思路:
只要求出 \(x=1,y=1\) 的情况就可以求出答案。
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] &= \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]\\ &= \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\varepsilon(\gcd(i,j))\\ &= \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|i,d|j}\mu(d)\\ &= \sum_{d \ge 1}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|\gcd(i,j)]\\ &= \sum_{d \ge 1}\mu(d)\lfloor\frac{n}{kd}\rfloor \lfloor\frac{m}{kd}\rfloor\\ \end{aligned} \]预处理 \(\mu\) 的前缀和,数论分块即可。
关键在于将 \([n=1]\) 转化为 \(\sum_{d|n}\mu(d)\) 与交换求和顺序。
但是这其实只是利用了 \(\sum_{d|n}\mu(d)=[n=1]\) 这个结论,并没有真正的用反演公式。
其实用反演公式会非常显然。
设 \(f(k)\) 表示 \(\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]\),\(f(d)\) 即是答案。
设 \(g(k)\) 表示 \(\sum_{i=1}^n\sum_{j=1}^m[k|\gcd(i,j)]\),显然有:
\[g(k)=\sum_{k|x}f(x) \]我们也可以直接计算出 \(g(k)=\lfloor\frac{n}{k}\rfloor \lfloor\frac{m}{k}\rfloor\)。
所以反演得到:
\[f(k) = \sum_{k | x}\mu(x)g(\frac{x}{k}) \]也就是枚举所有 \(k\) 的倍数,和之前的式子其实是一样的。
相对而言,我们去找 \(f\) 和 \(g\) 会比直接推式子简单一些。
题目2: 求 \(\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)\),\(1 \le n, m \le 10^7\)。(P1829 [国家集训队] Crash的数字表格 / JZPTAB)
思路:
推式子。
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j) &= \sum_{i=1}^n\sum_{j=1}^m\frac{ij}{\gcd(i,j)}\\ &= \sum_{k \ge 1} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]\frac{ij}{k}\\ &= \sum_{k \ge 1} \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]ijk\\ &= \sum_{k \ge 1} k \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]ij\\ \end{aligned} \]记 \(f(N,M)=\sum_{i=1}^{N}\sum_{j=1}^{M}[\gcd(i,j)=1]ij\),则:
\[\begin{aligned} f(N,M) &=\sum_{i=1}^{N}\sum_{j=1}^{M}[\gcd(i,j)=1]ij\\ &=\sum_{i=1}^{N}\sum_{j=1}^{M}ij\sum_{d|i,d|j}\mu(d)\\ &=\sum_{d \ge 1}\mu(d)\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}ijd^2\\ &=\sum_{d \ge 1}\mu(d)d^2\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}ij\\ \end{aligned} \]记 \(g(N,M)=\sum_{i=1}^{N}\sum_{j=1}^{M}ij\),显然 \(g(N,M)=\frac{NM(N+1)(M+1)}{4}\)。
所以上式等于:
\[\sum_{d \ge 1}\mu(d)d^2 g(\lfloor\frac{N}{d}\rfloor, \lfloor\frac{M}{d}\rfloor) \]记 \(h(n)=\mu(n)n^2\),显然是个积性函数,我们可以预处理它的前缀和,然后配合数论分块在 \(O(\sqrt N)\) 的时间内算出 \(f(N,M)\),最后的答案即为:
\[\sum_{k \ge 1} k f(\lfloor\frac{n}{k}\rfloor \lfloor\frac{m}{k}\rfloor) \]再次数论分块,调用 \(f(N,M)\) \(\sqrt n\) 次,所以最终的复杂度是 \(O(n)\) 的。
同理,我们也可以用反演公式来推。
记:
\[f(k)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]\frac{ij}{k}\]\[g(k)=\sum_{k|d}f(d) \]推一下 \(g(k)\):
\[\begin{aligned} g(k) &= \sum_{k|d}f(d)\\ &= \sum_{i=1}^n\sum_{j=1}^m[k|\gcd(i,j)]\frac{ij}{k}\\ &= \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]ijk\\ &= k\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]ij \end{aligned} \]然后就和上面的一样了。
题目3: 题意同上,多组询问,\(T \le 10^4,n,m \le 10^7\)。(BZOJ 2693)
思路:
很明显我们需要优化上题。
上题我们得到的式子:
\[f(N,M)=\sum_{d \ge 1}\mu(d)d^2 g(\lfloor\frac{N}{d}\rfloor, \lfloor\frac{M}{d}\rfloor) \]答案即为:
\[\sum_{k = 1}^n k f(\lfloor\frac{n}{k}\rfloor \lfloor\frac{m}{k}\rfloor) \]现在我们将 \(f\) 展开,代入答案得到:
\[\begin{aligned} \sum_{k = 1}^n k f(\lfloor\frac{n}{k}\rfloor \lfloor\frac{m}{k}\rfloor) &= \sum_{k = 1}^n k \sum_{d \ge 1}\mu(d)d^2g(\lfloor\frac{n}{dk}\rfloor \lfloor\frac{m}{dk}\rfloor)\\ \end{aligned} \]关键转化:令 \(T = dk\),将枚举 \((d,k)\) 改为枚举 \((T,d)\)。
上式变为:
\[\begin{aligned} \sum_{k = 1}^n k \sum_{d \ge 1}\mu(d)d^2g(\lfloor\frac{n}{dk}\rfloor \lfloor\frac{m}{dk}\rfloor) &= \sum_{T = 1}^n \sum_{d | T}\mu(d)d^2\frac{T}{d}g(\lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor)\\ &= \sum_{T = 1}^n g(\lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor)T\sum_{d | T}\mu(d)d\\ \end{aligned} \]令 \(h(T) = T\sum_{d|n}\mu(d)d\),这个函数是个积性函数,可以 \(O(n)\) 预处理出来前缀和。而 \(g(N,M)\) 是可以 \(O(1)\) 计算的。所以单次询问可以直接数论分块,时间复杂度 \(O(T\sqrt{n})\)。
转化非常关键!!!
题目4: 假设我们有一个集合 \(S \in \mathbb{Z_+}\),求:
\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j) \in S] \]思路:
这其实是一类问题:P2257 YY的GCD(\(S\) 是质数集合),HDU5663 Hillan and the girl(\(S\) 是平方数集合)。
其实都是一个方法。
我们先推式子:
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j) \in S] &= \sum_{d \in S}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j) =d]\\ &= \sum_{d \in S}\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d} \rfloor}[\gcd(i,j) =1]\\ &= \sum_{d \in S}\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d} \rfloor}\sum_{k|i,k|j}\mu(k)\\ &= \sum_{d \in S}\sum_{k \ge 1}\mu(k)\sum_{i=1}^{\lfloor \frac{n}{dk}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dk} \rfloor}1\\ &= \sum_{d \in S}\sum_{k \ge 1}\mu(k){\lfloor \frac{n}{dk}\rfloor}{\lfloor\frac{m}{dk} \rfloor}\\ \end{aligned} \]然后,还是刚才的关键转化:将 \((d,k)\) 换成 \((d, T)\)。
\[\begin{aligned} \sum_{d \in S}\sum_{k \ge 1}\mu(k){\lfloor \frac{n}{dk}\rfloor}{\lfloor\frac{m}{dk} \rfloor} &= \sum_{T=1}^n\sum_{d|T,d \in S}\mu(\frac{T}{d}){\lfloor \frac{n}{T}\rfloor}{\lfloor\frac{m}{T} \rfloor}\\ &= \sum_{T=1}^n{\lfloor \frac{n}{T}\rfloor}{\lfloor\frac{m}{T} \rfloor}\sum_{d|T,d \in S}\mu(\frac{T}{d})\\ \end{aligned} \]记 $f(T) =\sum_{d|T,d \in S}\mu(\frac{T}{d}) $,显然可以预处理出来,时间复杂度低于 \(O(n \log \log n)\),然后数论分块即可单次 \(O(\sqrt{n})\) 时间解决。
题目5: 多组询问,求:
\[\sum_{i=1}^n\sum_{j=1}^m\sigma(\gcd(i,j))[\sigma(\gcd(i,j)) \le a] \]思路:
同理,还是推式子,过程不写了,我们将原式化为:
\[\sum_{d=1}^n\sigma(d)[\sigma(d) \le a]\sum_{k \ge 1}\mu(k){\lfloor \frac{n}{dk}\rfloor}{\lfloor\frac{m}{dk} \rfloor} \]然后还是将 \((d,k)\) 变为 \((T,k)\) 可以变为:
\[\sum_{T=1}^n{\lfloor \frac{n}{T}\rfloor}{\lfloor\frac{m}{T} \rfloor}\sum_{d|T}[\sigma(d) \le a]\sigma(d)\mu(\frac{T}{d}) \]考虑到是多组询问,\(a\) 会变,我们将询问离线,按照 \(a\) 升序排序,然后依次将 \(\sigma(d)\) 从小到大加入贡献。
为了数论分块,我们要支持单点修改和区间查询,树状数组即可,时间复杂度 \(O(n \log \log n \log n)\)。
题目6: 多组询问,求:
\[\sum_{i=1}^n\sum_{j=1}^md(ij) \]\(d(n)\) 表示 \(n\) 的约数个数。(P3327 [SDOI2015] 约数个数和)
思路:
首先,我们有一个关于 \(d(ij)\) 的公式:
\[d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x, y)=1] \] 标签:lfloor,frac,gcd,乌斯,sum,rfloor,mu,反演,莫比 From: https://www.cnblogs.com/rlc202204/p/17976387