【CF1656H】Equal LCM Subsets

题意

给定集合 $A$ 和 $B$，从中选择两个子集 $A'\subseteq A,B'\subseteq B$ 满足 $\operatorname{lcm}(A')=\operatorname{lcm}(B')$ 。

满足 $\lvert A\rvert,\lvert B\rvert\le 10^3,A,B\le 4\times 10^{35}$。

思路

考虑将数 $A_i$ 分解为 $\prod\limits_{j=1}^{k}{p_j}^{\alpha_j}$，其中 $p\in \operatorname{prime}$。如果对于一个 $p_j$ 的 $\alpha_j$ 大于 $B$ 中所有的 $p_j$ 的 $\alpha_j$，那么 $A_i$ 必须被删除，对 $B$ 也同理。

通过上面的分析显然可以得到在满足一下情况时才会将 $A_i$ 删除：

$\gcd\limits_{i=1}^m \frac{A_x}{\gcd(A_x,B_i)}>1$

因为需要支持将 $B_i$ 进行单点删除，所以可以使用线段树进行快速维护。具体的，线段树维护 $\frac{A_x}{\gcd(A_x,B_i)}$ 的值，时间复杂度为 $O(n^2(\log W+\log n))$。

code