浅谈钬钊钶镭后缀和——「MCOI-02」Convex Hull 凸包 题解

推一下蒟蒻 $\color{green}{\texttt{博客}}$ ～

原题链接~

---

粗略捞了一眼题解区，觉得有些比较重要的细节不是很懂，自己瞎撞撞终于搞明白乐。/kk

所以本篇文章用于解释一些思维上的细节。

一、$\tau*\mu=1 $ ?

我们了解到 $\sum_{d|n} \mu(d)\cdot 1=[n=1]$ ，表达成卷积形式有：

$$1*\mu=\epsilon$$

而当我们展开 $\tau$ 可得：

$$\tau(n)=\sum_{d|n} 1\cdot 1$$ $$\tau=1*1$$

等式两边同卷 $\mu$ ：

$$\tau*\mu=1*1*\mu$$

用 $\epsilon$ 换 $1*\mu$ ：

$$\tau*\mu=1*\epsilon$$

因为 $1*\epsilon=1$ ，所以我们就证得了：

$$\tau*\mu=1$$

二、大众推柿子思路

_默认 $n<m$_

$$\sum^{n}_{i}\sum^{m}_{j}\tau(i)\tau(j)\tau(\gcd(i,j))$$ $$=\sum_{d}^{n}\tau(d)\sum^{n}_{i}\sum^{m}_{j}\tau(i)\tau(j)[\gcd(i,j)=d]\quad\texttt{随手枚举gcd}$$ $$=\sum_{d}^{n}\tau(d)\sum^{\lfloor\frac{n}{\color{red}d}\rfloor}_{i}\sum^{\lfloor\frac{m}{\color{red}d}\rfloor}_{j}\tau(i{\color{red}d} )\tau(j{\color{red}d})[\gcd(i,j)={\color{red}1}]\quad\texttt{随手除d}$$ $$=\sum_{d}^{n}\tau(d)\sum^{\lfloor\frac{n}{\color{red}d}\rfloor}_{i}\sum^{\lfloor\frac{m}{\color{red}d}\rfloor}_{j}\tau(i{\color{red}d})\tau(j{\color{red}d}){\color{green}\sum_{k|\gcd(i,j)}\mu(k)}\quad\texttt{随手套} \mu \texttt{性质}$$ $$=\sum_{d}^{n}\tau(d){\color{green}{\sum_{k}^{n}\mu(k)}}\sum^{\lfloor\frac{n}{\color{red}d\color{blue}k}\rfloor}_{i}\sum^{\lfloor\frac{m}{\color{red}d\color{blue}k}\rfloor}_{j}\tau(i{\color{red}d}{\color{blue}k})\tau(j{\color{red}d}{\color{blue}k})\quad\texttt{随手将}\mu\texttt{提前，拉出k}$$ $$={\color{purple}\sum _ {\color{purple}T}^{n}}\boxed{\sum_{d|{\color{purple}T}}\tau(d)\mu(\frac{\color{purple}T}{d})}\sum^{\lfloor\frac{n}{\color{purple}T}\rfloor}_{i}\tau(i{\color{purple}T})\sum^{\lfloor\frac{m}{\color{purple}T}\rfloor}_{j}\tau(j{\color{purple}T})\quad\texttt{随手用T代dk，枚举T}$$ $$={\color{purple}\sum_{\color{purple}T}^{n}}\sum^{\lfloor\frac{n}{\color{purple}T}\rfloor}_{i}\tau(i{\color{purple}T})\sum^{\lfloor\frac{m}{\color{purple}T}\rfloor}_{j}\tau(j{\color{purple}T})\quad\texttt{随手套用}\tau*\mu=1$$ $$={\color{purple}\sum_{\color{purple}T}^{n}}{\color{orange}\sum_{T|i}^{n}\tau(i)}{\color{orange}\sum_{T|j}^{m}\tau(j)}\quad\texttt{随手换个写法}$$

这样我们就有了一个看上去最终能用的式子。

此时复杂度不严格地说应该是一只 $\log$ ，众所不知，他跑不过去。如果你很松那另当别论。

我们着手狄利克雷后缀和优化后两个 $\sum$ 。

三、狄利克雷后缀和？

对于形如 ：

$$\sum_{T|i}f(i)$$

的式子，我们可以用狄利克雷后缀和优化到 $\mathcal{O}(n\log\log m)$

具体实现如下：

/*len——质数表长度；v[]——质数表；A[]——后缀和函数*/
for (int i = 0; i < len; i++)
{
	for (int j = N / v[i]; j; j--)//可以理解成考虑每个质因数对后缀和的影响
	{
		A[j] = (A[j] + A[j * v[i]]) % MOD;
	}
}

我们可以用这个来优化后两个 $\sum$ 。

最后获得了约为 $\mathcal{O}(n\log\log m)$ 的优秀复杂度。

---

码字不易，笔者叹气。

最后更新： 2021年04月21日 22:09

原始链接： https://quest233.github.io/2021/04/17/%E6%B5%85%E8%B0%88%E9%92%AC%E9%92%8A%E9%92%B6%E9%95%AD%E5%90%8E%E7%BC%80%E5%92%8C%E2%80%94%E2%80%94%E3%80%8CMCOI-02%E3%80%8DConvex-Hull-%E5%87%B8%E5%8C%85-%E9%A2%98%E8%A7%A3/

quest_2