题解：P8322 『JROI-4』少女幻葬

感觉前两篇题解的式子太意识流了。

记值域为 $m$。

由于 $\gcd(a_i,a_{i+1},a_{i+2})=k$，所以有 $k|a_i$。不妨令 $a_i\leftarrow\dfrac{a_i}{k},l_i\leftarrow\lceil\dfrac{l_i}{k}\rceil,r_i\leftarrow\lfloor\dfrac{r_i}{k}\rfloor$。则原限制转化为 $l_i\le a_i\le r_i,\gcd(a_i,a_{i+1})\neq 1,\gcd(a_i,a_{i+1},a_{i+2})=1$。接下来的 $k$ 和题目里的没有关系。

设一个状态转移会比较抽象。设 $f(i,j,k)$ 表示考虑到第 $i$ 个数，$a_i=k$，$\gcd(a_i,a_{i-1})=j$ 的方案数；设 $g(i,j,k)$ 表示考虑到第 $i$ 个数，$a_i=k$，$\gcd(a_i,a_{i+1})=j$ 的方案数。

首先是 $g$ 到 $f$ 的转移为 $f(i,j,k)=\sum\limits_{v=l_{i-1}}^{r_{i-1}}g(i-1,j,v)[\gcd(v,k)=j]$。

除掉 $j$ 后反演得到 $f(i,j,k)=\sum\limits_{v=\lceil\frac{l_{i-1}}{j}\rceil}^{\lfloor\frac{r_{i-1}}{j}\rfloor}g(i-1,j,vj)\sum\limits_{d|v,d|\frac{k}{j}}\mu(d)$。

即：

不妨 $k\leftarrow \dfrac k j$，对第三维做狄利克雷后缀和，对位乘 $\mu$ 后再做狄利克雷前缀和即可转移，时间复杂度 $O(nm\log m\log\log m)$，前一个 $\log m$ 是枚举因数的调和级数，后一个 $\log\log m$ 是狄利克雷前后缀和。

然后再是 $f$ 到 $g$ 的转移为：

枚举 $k$，把 $f(i,x,k)$ 贡献到 $x$ 的质因数集合的位置然后求高维后缀和，那么 $g(i,j,k)$ 就是 $j$ 的质因数集合的补集的位置。这一部分复杂度是 $\sum\limits_{k\le m}d(k)\omega(k)=\sum\limits_{k\le m}\omega(k)\sum\limits_{i|k}1=\sum\limits_{ik\le m}\omega(ik)\le\sum\limits_{ik\le m}(\omega(i)+\omega(k))=2\sum\limits_{i\le m}\sum\limits_{k\le\frac m i}\omega(i)=2\sum\limits_{i\le m}O(\dfrac m i\log\log\dfrac v i)=O(m\log m\log\log m)$。加上枚举第一维，总的复杂度是 $O(nm\log m\log\log m)$。

然后就做完了，时间复杂度 $O(nm\log m\log\log m)$。