上个星期kds给我看的题，第一眼不会做，然后稍微想了一下还是秒了。
感觉还是太简单了。
考虑到值域只有 \(300\)，我们这里假设 \(n\) 就是 \(300\)。重复的肯定开个桶记下来。
考虑经典结论：只会有至多一个质因子大于 \(17\)。
根据这个根号分治，那么我们记录 \(2^{0\sim 8}\times 3^{0\sim 5}\times 5^{0\sim 3}\times 7^{0\sim 2}\times 11^{0\sim 2}\times 13^{0\sim 2}\times 17^{0\sim 2}\) 这些状态。
对这个部分我们做 lcm 卷积，由于每个初始的元素只会有至多一个质因子大于 \(17\)。
考虑在每组元素的 lcm 处统计其可能的 lcm 之和，但是显然只能够在 lcm 的倍数处统计。
这个很简单，对权值做一个高维差分就行了。
而统计可能的 lcm 也非常简单。对于每个大于 \(17\) 的质因子开桶。因为质因子不同的部分互不相干所以可以写成类似下面这种形式：
\[\prod(p_i^{c_i}-p_i^{c_i+1}+p_i^{c_i+2}-...)\times(\prod((2^{cnt_i}-1)\times pri_i+1)-1) \]前面的 \(p,c\) 是不大于 \(17\) 的，后面的 \(pri,cnt\) 的大于 \(17\) 的。
于是接下来就很简单了。
复杂度大概是 \(O(17496\times 7\times\frac{n}{\ln n})\)，这个显然随随便便跑过去吧。
标签：17,LGP5616,times,因子,大于,lcm,sim From： https://www.cnblogs.com/lmpp/p/16803183.html