CF1285F Classical?

发表于 分类于 ， ， 阅读次数：

题意：给出数组 ，求 ，时限 。

特判 全同的情形。

显然 中相同的元素是无用的，可以先去个重。 考虑枚举 ，把所有 的倍数取出。

接下来，把他们都除以 ，问题转化成计算互质数对乘积的最大值。

从大到小枚举数，依次考虑 和比 大的集合 之间的贡献。

若发现有 使得 ，则贡献为 。

继续枚举时，只会枚举到 ，此时和某个满足 的 的可能的贡献为 。

所以，可以舍弃 所有 的数。

具体实现中，使用（从小到大的）单调栈,加入一个数 时,如果发现栈中存在某个数与 互质,则一路弹栈并计算贡献。

问题在于：如何判断栈中是否存在于 互质的元素。

我们需要一个数据结构，维护集合 ，支持加数，删数，查询是否有和 互质的数。这是经典问题。

维护 表示集合 中 的出现次数，则 中和 互质的数的个数是 维护 ，即 的倍数求和。加删数字时 ，相当于对 单点加减，即枚举 对 加减。

查询也是枚举因数。

单个问题复杂度为 ，问题总规模为 。

总复杂度为 。

改进：

对于任意 ,有 ，且 。

观察到 必然是 的因数，我们把每个数的所有因数加入，然后跑一遍互质的情况即可，复杂度为 。