题解：P15014 构造奶龙

· · 题解

这题一看这么难，考虑乱搞。

首先猜测答案肯定很小，实际上答案 \le 7。

那首先考虑一个做法，往序列里面依次插入 1 到 n，用链表维护，如果存在一个位置使得答案不增就直接插入即可，否则找到答案增量最小的位置插入。

判断两个数的最小公倍数的质因子个数可以预处理出来每个数的本质不同质因子个数，并用两个数的个数和减去最大公因数的个数即可，单次判断 O(\log n)。

该做法乍一看是 O(n^2)，实际上大部分的数找到对应位置的次数并不多，但如果你直接写这个也只能过 n \le 10^4，考虑离线所有询问，于是只用做一次上述做法，惊奇的发现可以通过 n \le 2\times 10^5。

那我们仍然考虑大部分的数找到对应位置的次数并不多，直接把找到对应位置的次数 >100 的打表出来发现只有 2100 多个，哦哦哦那不就打表存下来，理论时间复杂度为 O(100 \cdot n \log n)，实际上远远跑不满，因为大量数的找寻次数实际不到 10。

喜提当前最优解，最慢点 200 ms。

打表程序也放不上来，自己跑一个吧。