题解 P6810 【「MCOI-02」Convex Hull 凸包】

· · 题解

推一下蒟蒻 \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}{\red{d}}\rfloor}_{i}\sum^{\lfloor\frac{m}{\red{d}}\rfloor}_{j}\tau(i\red{d})\tau(j\red{d})[\gcd(i,j)=\red{1}]\quad\texttt{随手除d} =\sum_{d}^{n}\tau(d)\sum^{\lfloor\frac{n}{\red{d}}\rfloor}_{i}\sum^{\lfloor\frac{m}{\red{d}}\rfloor}_{j}\tau(i\red{d})\tau(j\red{d})\green{\sum_{k|\gcd(i,j)}\mu(k)}\quad\texttt{随手套} \mu \texttt{性质} =\sum_{d}^{n}\tau(d)\green{\sum_{k}^{n}\mu(k)}\sum^{\lfloor\frac{n}{\red{d}\blue{k}}\rfloor}_{i}\sum^{\lfloor\frac{m}{\red{d}\blue{k}}\rfloor}_{j}\tau(i\red{d}\blue{k})\tau(j\red{d}\blue{k})\quad\texttt{随手将}\mu\texttt{提前，拉出k} =\purple{\sum_{\purple{T}}^{n}}\boxed{\sum_{d|\purple{T}}\tau(d)\mu(\frac{\purple{T}}{d})}\sum^{\lfloor\frac{n}{\purple{T}}\rfloor}_{i}\tau(i\purple{T})\sum^{\lfloor\frac{m}{\purple{T}}\rfloor}_{j}\tau(j\purple{T})\quad\texttt{随手用T代dk，枚举T} =\purple{\sum_{\purple{T}}^{n}}\sum^{\lfloor\frac{n}{\purple{T}}\rfloor}_{i}\tau(i\purple{T})\sum^{\lfloor\frac{m}{\purple{T}}\rfloor}_{j}\tau(j\purple{T})\quad\texttt{随手套用}\tau*\mu=1 =\purple{\sum_{\purple{T}}^{n}}\orange{\sum_{T|i}^{n}\tau(i)}\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) 的优秀复杂度。

码字不易，笔者叹气。