[CF2183E] LCM is Legendary Counting Master 题解 & 被路由器做局了

菜完了，1:33 才写完 E，然后网络炸了没交上去，1:35 网络又好了，后来才知道是路由器 1:30 自动重启，被路由器做局了。

因为 单增，所以若 显然无解。考虑一种特殊情况，即 ，此时原式恰好等于 。考虑把 序列看成是从 中删了一些数，那么对于相邻两项 和 ，若不删除它们中间的数，那么贡献是 ；若删除它们中间的数，那么贡献是 。为了让删数过后原式 ，我们需要让 。简单推导得出，当且仅当 时上式取等。即 是好的的一个必要条件是 ，显然容易 DP。因为因数个数是 的，所以时间复杂度是 。

注意还有一个必要条件是 。

Submission。