前置知识:整除分块
结论:集合 \(\{x|\exists i\in \mathbb N^*,\lfloor \frac n i\rfloor =x\}\) 中的元素数量为 \(\sqrt n\) 级别个。具体来说,不超过 \(2\sqrt n\) 个。
证明:对于 \(i \le \sqrt n\),\(\lfloor \frac n i \rfloor\) 至多只有 \(\sqrt n\) 种取值;对于 \(i > \sqrt n\),\(\lfloor \frac n i \rfloor < \sqrt n\),也至多只有 \(\sqrt n\) 种取值。综上,对于所有的 \(i \in [1,n]\),\(\lfloor \frac n i \rfloor\) 至多只有 \(2\sqrt n\) 种取值。
应用:假设我们现在要求 \(\displaystyle\sum_{i=1}^n \lfloor \frac n i \rfloor\) 的值,且 \(n \le 10^{12}\)。
由于 \(\lfloor \frac n i \rfloor\) 的取值不超过 \(2\sqrt n\) 个,不难想到对于每个 \(x\) 统计 \(\lfloor \frac n i \rfloor=x\) 的 \(i\) 的数量。显然,所有的 \(i\) 一定恰好为一个区间 \([l,r]\)。假设我们已知 \(l\),容易发现 \(r\) 就是 \(\left \lfloor \frac{n}{\lfloor \frac n l \rfloor} \right \rfloor\),数量就是 \(r-l+1\) 个。还可以得知下一种取值的 \(l\) 就是当前取值的 \(r+1\)。
正题:莫比乌斯函数
定义:
\(\mu\) 是莫比乌斯函数。
\[\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases} \]性质:
-
\(\mu\) 是积性函数。
-
\(\displaystyle\sum_{d|n} \mu(d)=[n=1]\),其中当 \(x=1\) 时 \([x=1]\) 的值为 \(1\),否则为 \(0\)。
仅仅利用这两个性质就可以解决的问题:给出 \(n,m,v\),求满足 \(1 \leq x \leq n\),\(1 \leq y \leq m\),且 \(\gcd(x,y)=d\) 的二元组 \((x,y)\) 的数量。形式化的讲,求 \(\displaystyle \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=v]\)。
为了能够使用第二个性质,我们可以默认 \(i,j\) 都是 \(d\) 的倍数,所以 \(\displaystyle \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=v]=\displaystyle \sum_{i=1}^{\lfloor \frac n v \rfloor}\sum_{j=1}^{\lfloor \frac m v \rfloor}[\gcd(i,j)=1]\)
然后利用 \(\displaystyle\sum_{d|n} \mu(d)=[n=1]\),也就是 \([n=1]=\displaystyle\sum_{d|n} \mu(d)\),将 \([\gcd(i,j)=1]\) 化成 \(\displaystyle\sum_{d|\gcd(i,j)} \mu(d)\)。
那么原式就变成了 \(\displaystyle \sum_{i=1}^{\lfloor \frac n v \rfloor}\sum_{j=1}^{\lfloor \frac m v \rfloor}\displaystyle\sum_{d|\gcd(i,j)} \mu(d)\),改变枚举顺序,先枚举 \(d\),就是 \(\displaystyle\sum_{d=1}^{n}\mu(d)\lfloor \frac n {vd} \rfloor\lfloor \frac m {vd} \rfloor\)。再对 \(\lfloor \frac n {vd} \rfloor\lfloor \frac m {vd} \rfloor\) 进行整除分块,求一个 \(\mu\) 的前缀和即可。
更多:莫比乌斯变换
一般莫比乌斯变换有两种形式。
设 \(f(n),g(n)\) 是两个数论函数。
形式一:若 \(f(n)=\displaystyle \sum_{d|n}g(d)\),则有 \(g(n)=\displaystyle \sum_{d|n} \mu(d)f(\frac n d)\)。
形式二:若 \(f(n)=\displaystyle \sum_{n|d}g(d)\),则有 \(g(n)=\displaystyle \sum_{n|d} \mu(\frac d n)f(d)\)。
我们称 \(f(n)\) 为 \(g(n)\) 的莫比乌斯变换,\(g(n)\) 为 \(f(n)\) 的莫比乌斯逆变换(莫比乌斯反演)。
事实上,莫比乌斯函数的性质好像莫比乌斯反演出现的更加频繁。
总结
莫比乌斯反演是数论中的重要内容。对于一些函数 \(f(n)\),如果很难直接求出它的值,而容易求出其倍数和或约数和 \(g(n)\),那么可以通过莫比乌斯反演简化运算,求得 \(f(n)\) 的值。同时,它出现时的各种形式变化多端,十分有趣。
标签:lfloor,frac,函数,乌斯,sum,rfloor,mu,莫比,displaystyle From: https://www.cnblogs.com/Galetx/p/17264461.html