我们可以将一个集合划分为两个子集的方式的数量，使得两个子集中元素的乘积的 GCD 最小
Number of ways we can partition a set into two subsets such that the GCD of product of the elements in both subsets is minimum
我们有一个集合或一个唯一的正整数列表，其约束条件是列表或集合的大小可以达到 10000。objective 是将列表分成 2 个非空子集，例如GCD(Prod1, Prod2) == 1，其中 Prod1 是子集 1 中所有元素的乘积，Prod2 是子集 2 中所有元素的乘积。
例如
输入：
5 1 2
输出：
6
6个满足条件的子集
{1}, {2, 5} = gcd(1, 10) = 1
{1, 2}, {5} = gcd(2, 5) = 1
{1, 5}, {2} = gcd(5, 2) = 1
{2, 5}, {1} = gcd(10, 1) = 1
{5}, {1, 2} = gcd(5, 2) = 1
{2}, {1, 5} = gcd(2, 5) = 1
输入：
2 3 6
输出：
0
因为没有满足条件的子集
我通过生成所有 2 路分区并找到它的产品，然后采用它的 gcd 尝试了蛮力方法。但显然，这至少需要 O(N^2) 或更多，而且考虑到约束条件，这是不可行的。有没有更好的方法使用动态编程就像 subset-sum/difference 问题或使用任何其他 algorithm/data 结构？
正如 Michael Butscher 所观察到的，每两个不互质的正整数必须在分区的同一侧。事实证明这是充分必要条件。
制作一个图，其顶点是给定的正整数，其边表示不互质的整数对。计算此图中连通分量 k 的数量。 Return 2k − 2 因为独立，每个组件可以在分区的左侧或右侧，减去每个组件都在同一侧的 2 个退化分区.
我们有一个集合或一个唯一的正整数列表，其约束条件是列表或集合的大小可以达到 10000。objective 是将列表分成 2 个非空子集，例如GCD(Prod1, Prod2) == 1，其中 Prod1 是子集 1 中所有元素的乘积，Prod2 是子集 2 中所有元素的乘积。
例如
输入：
5 1 2
输出：
6
6个满足条件的子集
{1}, {2, 5} = gcd(1, 10) = 1
{1, 2}, {5} = gcd(2, 5) = 1
{1, 5}, {2} = gcd(5, 2) = 1
{2, 5}, {1} = gcd(10, 1) = 1
{5}, {1, 2} = gcd(5, 2) = 1
{2}, {1, 5} = gcd(2, 5) = 1
输入：
2 3 6
输出：
0
因为没有满足条件的子集
我通过生成所有 2 路分区并找到它的产品，然后采用它的 gcd 尝试了蛮力方法。但显然，这至少需要 O(N^2) 或更多，而且考虑到约束条件，这是不可行的。有没有更好的方法使用动态编程就像 subset-sum/difference 问题或使用任何其他 algorithm/data 结构？
正如 Michael Butscher 所观察到的，每两个不互质的正整数必须在分区的同一侧。事实证明这是充分必要条件。
制作一个图，其顶点是给定的正整数，其边表示不互质的整数对。计算此图中连通分量 k 的数量。 Return 2k − 2 因为独立，每个组件可以在分区的左侧或右侧，减去每个组件都在同一侧的 2 个退化分区.