Black Moonrise 题解

2019-05-07 17:08:19


Black Moonrise 题解

本题的出题人是我,本着100%口胡的传统,在之前确实没有发现这是一道原题,这里向大家表示深深的歉意

本题是一道非常好的莫比乌斯反演入门题,同时说明了信仰的重要性

就码量来讲个人觉得还是非常良心的

可能是全场最简单的题

算法1

按照题意描述模拟,每次询问直接枚举每一对宇宙碎片,时间复杂度$O(qn^2\log n)$

可以获得$10$分的好成绩

算法2

考虑优化算法$1$,显然这串数列两两的$gcd$是可以预处理出来的,预处理时间复杂度$O(n^2\log n)$

然后就可以做到每次询问$O(n^2)$回答

但是出题人很不要脸地卡了这种算法,所以正常情况下你仍然只有$10$分

原因很简单,你多了常数$2$

每次暴力统计答案的时候可以做到$O(\frac{1}{2}n^2)$统计,最后再将答案乘以$2$

由于$(i,i)$这样的对统计了两次,所以再减去这一段的和即可

由于数据随机,可以证明此时的复杂度大约为$O(\frac{1}{12}n^3)$,可以通过第二个测试点

算法3

题目中所给的式子用线段树不是很好维护,但增加/减少一个点的信息很好维护,所以可以使用莫队

加入/删除一个点的时候$O(n)$,使用前缀和可以做到$O(1)$

但是仍然需要处理原数组两两的$gcd$,所以只能得到$40$分

时间复杂度$O(n^2\log n+q\sqrt{n})$

算法4

前置芝士:莫比乌斯反演

设$F(x)$表示区间中$gcd$恰好为$x$的数对数量,那么显然有

$$ ans=\sum_{i=1}^{\infty} xF(x) $$

再设$G(x)$表示区间中$gcd$为$x$或$x$的倍数的数对数量,我们可以得到

$$ G(x)=\sum_{x|d}F(d) $$

反演一下

$$ F(x)=\sum_{x|d}\mu(\frac{d}{x})G(d) $$

可以得出

最后那个式子是一个狄利克雷卷积

即$(id*\mu)(x)$

我们知道$1*\varphi=id,1*\mu =e$

所以

所以

$$ ans=\sum_{d=1}^\infty G(d)\varphi(d) $$

其实如果不会将最后那个式子变成$\varphi$,$n\log n$预处理也是可以的

我们知道

$$ G(d)=(\sum_{i=l}^r[d|a_i])^2 $$

莫队的时候维护这个东西,每次枚举$a$的因数更新,需要预处理约数以及$\varphi$

时间复杂度$O(n\sqrt{n} \log n)$

注:由于一些奇妙的原因导致中间的公式挂了,所以只能用图片补一补了