Black Moonrise 题解

· · 个人记录

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)

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