CF1516D Cut 题解

一道套路题，做过同类型的题目应该能够直接看出做法。

这道题首先询问方式很像 DS 题的询问方式，但是实际上你会发现这道题做法是不能纯 DS 的，或者说这道题根本就不需要 DS。

发现如果乘积和 LCM 要相同的话需要满足这个区间内没有任意两个数最大公约数大于 1，而最大公约数可以归约到质因数上。

所以首先对每个数做一个质因数分解，然后考虑预处理出 \(r_i\) 表示第 \(i\) 个位置不断往右边扩展，能够扩展到的最右边的位置是什么，满足 \([i,r_i]\) 合法，且 \([i,r_i+1]\) 不合法或者是 \(r_i。

这个实际上开一个 \(cnt\) 数组双指针扫一遍就可以了，没必要使用什么高端 DS 技巧。

然后就是套路倍增了，设 \(f_{i,j}\) 表示 \(i\) 往右边跳 \(2^j\) 个区间之后能够到达的右端点，那么 \(f_{i,j}=f_{\min\{f_{i,j-1}+1,n\},j-1}\)。

然后查询的时候我们直接仿照倍增求 LCA 的时候往右边跳就可以了。

Code：GitHub CodeBase-of-Plozia CF1516D Cut.cpp