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)$ 注：由于一些奇妙的原因导致中间的公式挂了，所以只能用图片补一补了