计算将集合划分为两非空子集且子集乘积GCD为1的可行方案数

核心数论推导 #

两个子集乘积的GCD(Prod1, Prod2) = 1，等价于两个子集没有公共质因子。如果存在任意质数p同时出现在两个子集的元素的质因数分解中，那么p会同时整除Prod1和Prod2，GCD至少为p≥2，不满足要求。
由此可以推出约束：所有共享同一个质因子的数，必须被划分到同一个子集内，不能拆分到两个子集。 #

算法实现步骤 #

我们可以用并查集（Disjoint Set Union, DSU）来处理上述的绑定关系，步骤如下：

1. 质因数分解：对集合中的每个数做质因数分解，保留每个数的不重复质因子即可，不需要记录质因子的幂次。
2. 并查集合并：
   • 将集合中的每个元素作为并查集的独立节点，也可以引入质因子作为虚拟节点简化合并操作：比如给集合元素分配编号0~n-1，质因子p对应的虚拟节点编号设为n+p，将每个元素和它的所有质因子对应的虚拟节点执行合并操作。
   • 没有质因子的数字1，不会和任何其他节点合并，天然作为独立的连通块。
3. 统计连通块数量：合并完成后，统计所有有效连通块的总数量k。
4. 计算最终结果：每个连通块可以选择划到子集1或者子集2，总共有2^k种分配方式，减去两种非法情况（所有连通块都划到子集1导致子集2为空，或者都划到子集2导致子集1为空），最终答案为2^k - 2。

示例验证 #

• 示例1输入：{5,1,2}
  质因数分解：1无质因子，2的质因子为2，5的质因子为5，合并后总共有3个独立连通块，答案为2^3 - 2 = 6，和示例输出一致。
• 示例2输入：{2,3,6}
  质因数分解：2的质因子为2，3的质因子为3，6的质因子为2和3。合并后2、3、6都属于同一个连通块，k=1，答案为2^1 -2 = 0，和示例输出一致。

复杂度分析 #

• 时间复杂度：主要由质因数分解和并查集操作构成，假设集合元素最大值为M，n为集合规模，质因数分解的时间复杂度为O(n*√M)，如果提前筛出√M范围内的素数可以进一步优化分解速度，1e4规模的输入可以轻松处理。
• 空间复杂度：并查集的空间占用和元素数量+质因子数量成正比，完全在可接受范围内。

内容的提问来源于stack exchange，提问作者Joshin Rexy