Möbius反演可用于简化对于某些数论问题的计算:对于\(f(x)\),我们可以构造出(至少是试图构造出)一个更加简单的\(F(x)\),并应用这一定理将对\(f(x)\)的计算化为对\(\mu(x)\)和对\(F(x)\)的计算。
问题:$$\forall n m i j, \sum_{i = 1}^n\sum_{j = 1}^m[gcd(i,j) = 1] = ?$$
让我们先来考察一下直接计算的复杂度。
- 判断\(gcd(i,j)=1\)需要的时间是计算出\(gcd(i,j)\)的时间与判断其是否为1的时间之和,是\(O(logk)\);
- 这一操作要经历两层循环(\(\sum_{i=1}^n\sum_{j=1}^m\)),是\(O(nm)\)。
总复杂度为\(O(nmlogk)\),其中k为\(min(n,m)\);在competitive programming中,n和m的范围一般都是一样的,所以复杂度可以计为\(O(n^2logn)\)。那么这样的复杂度能够承受多大的范围呢?按照以往的经验,1000ms对应\(1\times 10^8\tilde{}2\times 10^8\),因此保守计算(在1000ms的限制下)n最大可以有\(10^3\),这显然是不够的。
试图对其应用Möbius反演:
$$\sum_{i=1}^n\sum_{j=1}^m\sum_{d \mid gcd(i,j)}\mu(d)$$
实际上也就是:
$$\sum_{i=1}^n\sum_{j=1}^m\sum_{x=1}^{min(i,j)}[x\mid gcd(i,j)]\mu(d)$$
理由很简单:只有当\(x \mid gcd(i,j)\)时才会有\(\mu(d)\times 1\),于是就相当于只加了\(d \mid gcd(i,j)\)的\(\mu(d)\)。
而这实际上等于:
$$\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{min(i,j)}[d|i][d|j]\mu(d)$$
假如我们先遍历可能的\(d\),这实际上就是:
$$\sum_{d=1}^{k}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{m}[d|i][d|j]$$
有一个直观的理由:先计算要不要取(即\([d|i][d|j]\))然后再计算\(\mu(d)\),与先计算\(\mu(d)\)然后再决定是否取,结果是一样的。由上可得:
$$\sum_{d=1}^{k}\mu(d)\left(\sum_{i=1}^{n}[d|i]\right)\left(\sum_{j=1}^{m}[d|j]\right)$$
易知有\(\sum_{i=1}^n[d|i] = \lfloor \frac{n}{d}\rfloor\),于是实际上就是:
$$f(x) = \sum_{d=1}^{k}\mu(d)\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor$$
其中\(k = min(n,m)\)。对其分析复杂度:\(\mu(d)\)可以用\(O(n)\)的时间使用线性筛先行计算,在这一等式中\(\mu(d)\)应视为\(O(1)\);我们可以直接遍历\([1..min(n,m)]\),时间复杂度为\(O(n)\);总计时间复杂度为\(O(n)\)。于是,通过使用Möbius反演,我们将原本\(O(n^2logn)\)的计算转变成了\(O(n)\)的计算。
HDU 1695
问题:$$\forall b d k, \sum_{i = 1}^n\sum_{j = 1}^m[gcd< i,j> = k] = ?$$
其中规定\(<i,j> = <j,i>\)。
对于其中的规定先不管(因为可以用简单地用「全部 - 重复部分」的方法解决;而「重复部分」的计算与「全部」的复杂度是一样的),其复杂度跟上一个问题是一样的,为\(O(bdlogk)\),而规定本身对复杂度没有影响。那么,要怎么办呢?
- 定义\(f[n,m](k) = \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j) = k]\),再定义:\begin{align}
F[n,m](k) & = \sum_{k \mid d} f[n,m](d) \\ & = f[n,m](k)+f[n,m](2k)+f[n,m](3k)+\cdots \\ & = \sum_{x=1}^{\lfloor {\frac{min(n,m)}{k}} \rfloor}f[n,m](xk) \end{align}。为什么是\(\lfloor \frac{min(n,m)}{k} \rfloor\)?是因为这里的\(k\)实际上是受限的:\(f\)的定义中有\(gcd(i,j)=k\),可知\(k\)最大只能是\(min(i,j)\),即\(min(n,m)\)。
- 通过第二类Möbius反演得到\(f[n,m](k) = \sum_{x=1}^{\lfloor {\frac{min(n,m)}{k}} \rfloor}\mu(x)F[n,m](xk)\)。
- 考察\(F[n,m](k)\)。实际上有:\begin{align} F[n,m](k) & = f[n,m](k)+f[n,m](2k)+\cdots \\ & = \sum_{i=1}^n\sum_{j=1}^m[k | gcd(i,j)] \\ & = \lfloor \frac{n}{k} \rfloor \lfloor \frac{m}{k} \rfloor \end{align}
- 整合得\(f[n,m](k) = \sum_{i=1}^{\lfloor \frac{min(n,m)}{k} \rfloor}\mu(i)\lfloor \frac{n}{ik} \rfloor \lfloor \frac{m}{ik} \rfloor \)
考察其复杂度:对于\(\lfloor \frac{min(n,m)}{k} \rfloor\),最坏情况有\(\lfloor \frac{min(n,m)}{k} \rfloor \sim min(n,m) \sim n\),即\(O(n)\);\(F[n,m](k)\)的计算很容易知道是\(O(1)\);对于\(\mu\),可以先进行\(O(nlogn)\)的直接按定义计算或\(O(n)\)的线性筛进行计算。于是总体复杂度为\(O(nlogn+n\times 1) \sim O(nlogn)\)或者\(O(n)\)(使用线性筛)。
HYSBZ 2005
要意识到题目中的\(k\)实际上是\(gcd(i,j)-1\)。于是问题为:$$\forall n m, \sum_{i=1}^n\sum_{j=1}^m\left[2(gcd(i,j)-1)+1\right] = ?$$
但是我们不直接对此构造\(f(k)\);即,我们不计算\(2(gcd(i,j)-1)+1\)的和,而是计算\(gcd(i,j)=k\)的个数与\(2k+1\)的乘积;这样就将问题变成了计算\(\sum_{k}\left[(2k+1)\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]\right]\)。与上一个问题类似,这里的\(k\)也是受限的。计算的总复杂度为\(O(n^2)\)。