首先有一个暴力的想法：依次查看左边每个数，对于左边每个数，计算右边未被删除的点与这个点的 \(\gcd\) 的 \(LCM\)，如果这个 \(LCM\) 等于当前这个数，说明这个点可以被左边的 \(LCM\) 整除，否则说明这个点不能整除，需要删掉。对于右边同理。这样暴力删除复杂度是 \(O(n^3\log A)\) 的。
考虑删除一个数的时候对这半边的影响，这只会让某些质因子的幂次从最大值变成次大值。考虑两个数 \(a,b\)，\(\frac{a}{\gcd(a,b)}\) 中的质因子是 \(a\) 严格幂次大于 \(b\) 的质因子，可以提取出这些质因子，就得到了 \(a\) 对于 \(LCM\) 的贡献。将这些贡献换成次大值之后遍历右边每个数，如果这个数除掉次大值之后仍然和原来的最大值 \(\gcd>1\)，则右边的这样的数都需要删掉。因此我们可以以 \(O(n\log A)\) 的代价删掉一个数，总复杂度 \(O(n^2\log A)\)。
因为 \(A\) 特别大，并且取 \(\gcd\) 的次数有点多，跑得很慢。submission
标签：CF1656H,log,删掉,Equal,因子,次大值,LCM,gcd From： https://www.cnblogs.com/275307894a/p/17635973.html