CF2241G Summmon 题解

· · 题解

题目传送门：CF2241G Summmon

贡献一个无脑的双 \log 做法。

题目分析

首先根据裴蜀定理，若 \gcd\limits_{j=1}^{i-1} b_j 同时也是 b_i 的因数，则 b_i 是可以变成 b_{i-1} 的。也就是说可以将序列缩成 c_1 \sim c_k，使得其前缀 \gcd 单减。经典结论 k 是 O(\log) 的。

到这已经可做了，一种想法是倒序枚举起始点，单调栈维护 c，每个 c_i 肯定都在 c_1 两侧浮动，即模前缀 \gcd 同余的周期里选最近的两个。问题转化为对每个 i \in (1,k] 给出 l_i,r_i 两个选择，最小化极差。

自然可以按 r 排序，枚举最后一个选 r 的元素即可。时间复杂度 O(n \log^2)。（好像是 \log^2 \cdot \log\log？）