前置：积性函数与狄利克雷卷积 和 整除分块
两个基础积性函数：\(\varepsilon(n)=[n=1]\)，\(1(n)=1\)。
性质：\(\varepsilon*f=f\)，\(f\) 是任意函数。
结论：\(f(n)\) 是积性函数 \(\iff g(n)=\displaystyle\sum_{d|n}f(d)\) 是积性。
证明：
$\Rightarrow $ 方向：\(g=f*1\)，狄利克雷卷积的性质在前置里面证了。
\(\Leftarrow\) 方向：归纳法。
-
\(g(1)=f(1)\)。由于 \(g\) 积性，所以 \(g(1)=g(1)g(1)\)，所以 \(g(1)=f(1)=1\)。
-
对于 \(n>1\)，设 \(n=ab,\;(a,b)=1\)。归纳法知 \(f(1)\sim f(n-1)\) 是积性函数。
注意一下，当 \(d_1=a,d_2=b\) 时，\(d_1d_2=n\)，这里我们还不知道 \(f(n)\) 是积性的。所以我们要把这种情况拆出来单独考虑。
\[=\displaystyle(\sum_{d_1|a}\sum_{d_2|b}f(d_1)\cdot f(d_2))-f(a)f(b)+f(ab) \]另外，有条件 \(g\) 是积性函数，所以
\[g(n)=g(a)g(b)=\displaystyle\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) \]两个式子对比一下，得到 \(f(a)f(b)=f(ab)\)，所以 \(f(n)\) 也是积性函数。归纳法证毕。
莫比乌斯函数：定义 \(\sum_{d|n}\mu (d)=\varepsilon(n)\) 的函数 \(\mu\) 称莫比乌斯函数。
性质1：\(\mu\) 是积性函数。
证明：在开头的前置里证明过这个结论。因为 \(\varepsilon\) 是积性函数，所以 \(\mu\) 也是积性函数。
性质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$}\\ (-1)^k & \text{其他情况} \end{cases}\]证明：用前两个性质易得。
性质4：\(\mu*1=\varepsilon\)。
莫比乌斯反演两个公式：
-
\(g(n)=\sum_{d|n}f(n)\iff f=\mu*g\)。
-
\(g(n)=\sum_{n|d}f(n)\iff f(n)=\sum_{n|d}\mu*f\)，注意这个公式的 \(d\) 是一直变大直到 \(+\infty\) 的。
只证明一：由狄利克雷卷积的结合律、交换律：
\[g(n)=\sum_{d|n}f(n)=f*1 \]所以
\[\mu*g=\mu*(f*1)=(\mu*1)*f=\varepsilon*f=f \]显然这个等式从哪个方向都可以推出来。
【应用】
- 注意 \(\sum_{d|n}\mu(d)=\varepsilon(n)\)。也很有用。
求 \(\displaystyle\sum_{i=1}^a\sum_{j=1}^b[gcd(a,b)=d]\)，\(a,b,d\le 5e4\)。有多组测试数据，最多 \(5e4\) 组。
常用变形： \(gcd(a,b)=d\iff gcd(\frac{a}{d},\frac{b}{d})=1\)，然后用 \(\sum_{d|n}\mu(d)=\varepsilon(gcd(\frac{a}{d},\frac{b}{d}))\) 转化。
回到正题。
\[\text{原式}=\displaystyle\sum_{i=1}^a\sum_{j=1}^b[d|i]\times [d|j]\times [gcd(\frac{i}{d},\frac{j}{d})=1] \]既然 \(i,j\) 是 \(d\) 的倍数，我们不如直接枚举 \(i'=i/d,j'=j/d\)
\[=\displaystyle\sum_{i'=1}^{[\frac{a}{d}]}\sum_{j'=1}^{[\frac{b}{d}]}[gcd(i',j')=1] \]莫比乌斯函数性质：\(\sum_{d|n}\mu(d)=\varepsilon(n)\)
\[=\displaystyle\sum_{i'=1}^{[\frac{a}{d}]}\sum_{j'=1}^{[\frac{b}{d}]}\sum_{k|gcd(i',j')}\mu(k) \]\[=\displaystyle\sum_{i'=1}^{[\frac{a}{d}]}\sum_{j'=1}^{[\frac{b}{d}]}\sum_{k|i',k|j'}\mu(k) \]同样，既然 \(i',j'\) 是 \(k\) 的倍数，不如先枚举 \(k\)。记 \(A=[\frac{a}{d}],B=[\frac{b}{d}]\)。
\[=\displaystyle\sum_{k=1}^{\min(A,B)}\sum_{i''=1}^{[\frac{A}{k}]}\sum_{j''=1}^{[\frac{B}{k}]}\mu(k) \]\[=\displaystyle\sum_{k=1}^{\min(A,B)}[\frac{A}{k}][\frac{B}{k}]\mu(k) \]发现 \([\frac{A}{k}][\frac{B}{k}]\) 的取值是 \(O(\sqrt A)\) 的，可以整除分块。
为什么是 \(O(\sqrt A)\) 的？把 \([\frac{A}{k}]\) 的函数图像画出来，是阶梯式下降的，每一层阶梯就是一个取值区间。而 \([\frac{B}{k}]\) 的函数图像最多把 \([\frac{A}{k}]\) 再多分割出一倍。
整除分块后，就是对一个区间的 \(\mu\) 求和，可以用前缀和。
复杂度 \(O(\sqrt A)\)。
\[\sum_{i=1}^n\sum_{j=i+1}^ngcd(i,j),n\le 2\times 10^6 \]这里有一个经典 trick: 枚举 \(gcd\) 然后统计个数。
\[\sum_{g=1}^ng\times \sum_{i=1}^{[\frac{n}{g}]}\sum_{j=i+1}^{[\frac{n}{g}]}[gcd(i,j)=1] \]记 \(G=[\frac{n}{g}]\)。注意这里又可以用 \(\varepsilon(gcd(i,j))\) 了。
\[\sum_{g=1}^ng\times \sum_{i=1}^G\sum_{j=i+1}^G\sum_{d|i,d|j}\mu(d) \]先枚举 \(d\)。
\[\sum_{g=1}^ng\sum_{d=1}^G\sum_{i=1}^{[\frac{G}{d}]}\sum_{j=1}^{[\frac{G}{d}]}\mu(d) \]\[\sum_{g=1}^ng\sum_{d=1}^G\mu(d)\cdot\sum_{i=1}^{[\frac{G}{d}]}\sum_{j=1}^{[\frac{G}{d}]}1 \]\[\sum_{g=1}^ng\sum_{d=1}^G\mu(d)\cdot\frac{1}{2}[\dfrac{G}{d}]([\dfrac{G}{d}-1]) \]对 \([\dfrac{G}{d}]\) 进行数论分块。
复杂度：对于每一个 \(g\)，复杂度是 \(O(\sqrt G)=O(\sqrt{\dfrac{n}{g}})\) 的。
总复杂度 \(O(\displaystyle\sum_{g=1}^n\sqrt{\frac{{n}}{{g}}})=O(\sqrt n+\sqrt \frac{n}{2}+\cdots)<O(n+\dfrac{n}{2}+\cdots)=O(n\log n).\)
经典题。求 \(\displaystyle\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)\)，\(n,m\le 10^7\)。
不妨 \(n\le m\)。
\[\text{原式}=\sum_{i=1}^n\sum_{j=1}^m\dfrac{i\cdot j}{gcd(i,j)}=\sum_{g=1}^{n}\sum_{i=1}^{[n/g]}\sum_{j=1}^{[m/g]}\dfrac{ijg^2}{g}\cdot[gcd(i,j)=1] \]\[=\sum_{g=1}^ng\sum_{i=1}^{[n/g]}\sum_{j=1}^{[m/g]}ij\cdot\sum_{d|i,d|j}\mu(d) \]记 \([n/g]=N,[m/g]=M.\)
\[=\sum_{g=1}^ng\sum_{d=1}^N\mu(d)\sum_{i=1}^{[N/d]}\sum_{j=1^{}}^{[M/d]}ij \]其中 \(\sum_{i=1}^{[N/d]}\sum_{j=1^{}}^{[M/d]}ij\) 是可以 \(O(1)\) 求得的。
记 \(f(x,y)=\sum_{d=1}^x\mu(d)\sum_{i=1}^{[x/d]}\sum_{j=1}^{[y/d]}ij\)。
则 \(\text{原式}=ans(n)=\displaystyle\sum_{g=1}^ng\cdot f([\dfrac{n}{g}],[\dfrac{m}{g}]).\)
在求 \(ans(n)\) 的时候用整除分块 \([\dfrac{n}{g}],[\dfrac{m}{g}]\)；在求 \(f()\) 的时候再整除分块。
复杂度 \(O(\sqrt n\cdot \sqrt N)<O(n).\)
.
标签：frac,gcd,积性,乌斯,sum,mu,反演,莫比,displaystyle From： https://www.cnblogs.com/FLY-lai/p/18000545