题解：P14009 数字游戏

· · 题解

省流：我算错复杂度了，这下你们这些 O(n\sqrt V \log n) 的老哥不能说是被卡常了吧

看见 \gcd，下意识想到莫比乌斯反演，于是来推一波式子。

f(l,r)=\sum^{a_l}_{b_1=1}\sum^{a_{l+1}}_{b_2=1}\sum^{a_{l+2}}_{b_3=1}\dots\sum^{a_{r}}_{b_{r-l+1}=1} [gcd(b_1,b_2,b_3,\dots,b_{r-l+1})=1] =\sum^{V}_{k=1}\mu (k) \sum^{a_l}_{b_1=1}\sum^{a_{l+1}}_{b_2=1}\sum^{a_{l+2}}_{b_3=1}\dots\sum^{a_{r}}_{b_{r-l+1}=1} [k|b_1][k|b_2]\dots[k|b_{r-l+1}] =\sum^{V}_{k=1}\mu (k) \lfloor \frac{a_l}{k} \rfloor \lfloor \frac{a_{l+1}}{k} \rfloor \dots \lfloor \frac{a_{r}}{k} \rfloor

我们要求的是

\sum^{n}_{l=1} \sum^{n}_{r=l}f(l,r) =\sum^{n}_{l=1} \sum^{n}_{r=l} \sum^{V}_{k=1}\mu (k) \lfloor \frac{a_l}{k} \rfloor \lfloor \frac{a_{l+1}}{k} \rfloor \dots \lfloor \frac{a_{r}}{k} \rfloor =\sum^{V}_{k=1}\mu (k) \sum^{n}_{l=1} \sum^{n}_{r=l} \lfloor \frac{a_l}{k} \rfloor \lfloor \frac{a_{l+1}}{k} \rfloor \dots \lfloor \frac{a_{r}}{k} \rfloor

不难发现，后面一堆东西就是所有区间的乘积之和，线段树上分别维护区间前缀积之和，后缀积之和，区间乘积，以及区间的答案，合并是可以很方便维护的。

但是，前面带了 O(V) 的循环，这样时间复杂度是爆表的。

但是这个整除很有性质，我们可以类似整除分块进行操作，整除一共只会有 O(\sqrt V) 种取值，所以可以提前预处理出来在哪些 k 整除的值会变化，暴力单点修改，复杂度是 O(n\sqrt V \log n)。

但是由于线段树巨大常数，这样还是有点慢，可以发现变化集中在前 O(\sqrt V)，每个都暴力去修改不划算。索性将前 O(\sqrt V) 个 k 的取值暴力重构修改，这样程序跑得飞快。

实际上，将前 600 个暴力重构时跑得最快。但是为了选手复杂度正确不被卡常，时限开到阈值取 O(\sqrt V) 能通过。

update

这份题解是我一年前写的，当我看见 https://www.luogu.com.cn/ticket/CCWV806064 的时候我就意识到自己算错了。

事实上，当你取阈值为 B 的时候，重构复杂度是 O(Bn)，单点修改复杂度是 O(n{V\over B}\log n)，经典均值不等式得到 B=\sqrt{V\log n} 的时候复杂度是 O(n\sqrt{V\log n})。