最大化二分法的 GCD（最大公约数）之和？
Maximize the sum of GCDs (Greatest Common Divisors) of a bipartition?
给定一个正数数组。我想将数组分成 2 个不同的子集，使它们的 gcd（最大公约数）之和最大。
示例数组：{6,7,6,7}.
答案：需要的两个子集是：{6,6}和{7,7}；他们各自的gcd是6和7，他们的sum = 6+7=13；这是可能的最大 gcd 总和。
Gcd: {8,12} 的 Gcd 是 {4} 因为 4 是除 8 和 12 的最大数。
注意：gcd(X)=X 如果子集只包含一个元素。
我的方法：通过暴力破解，找到数组所有可能的子序列，然后找到最大和，但是如果输入大小大于30个数字，这不起作用。我正在寻找更有效的方法。
Extra(s): 任何输入数字的最大大小为 10^9 ，时间限制：-1s 似乎不错，输入大小可能与 10^5
一样大
我觉得这其实是一个容易的问题。
首先，让我们忽略值出现不止一次的可能性。显然，最好将一个值的所有副本放在同一个集合中，因为将其中一些副本移到别处只会损害 GCD（edit: 除非只有一个不同的值） .所以我们假设所有元素都是不同的。另外，令 M 为任何元素的最大值。
这样想：有一个简单的解决方案，将最高元素放在一侧，将所有其余元素放在另一侧。 "All the rest" - GCD 可能为 1（当然可能更高），因此此解决方案为您提供 M+1。
具有多个不同元素的任何输入子集的 GCD 都不能高于 M/2（因为这样的除数必须乘以另一个至少为 2 的除数才能得到原始值，不高于 M)。所以 edit: 最优解不能由两个集合组成，每个集合都有多个不同的元素。它必须是一个元素与所有其他元素。
现在考虑 两个 最高元素，其中一些 d 的值为 M 和 M-d。如果我们都不选择它们作为单例，则它们都在 large-group 侧，这意味着该组最多具有 GCD d（因为如果 g|M 和 g|M-d 则 g| d);并且单例的贡献不会超过M-d-1。所以总分最多为 M-1——也就是说，小于我们在选择最高值时得到的分数。 因此，输入中的最高值或 second-highest（不同的）值必须在其自身的集合中。
因此您必须执行以下操作：
- 处理只有一个不同值的琐碎情况。
- 否则，获取最高的2个元素；.
- 计算所有 n-2 个最低元素的 GCD g_0。
- 计算 GCD 的 g_with_highest = GCD(g_0, M) 和 g_with_second_highest = GCD(g_0, M-d).
- 通过比较M + g_with_second_highest和(M-d) + g_with_highest选择单例。
给定一个正数数组。我想将数组分成 2 个不同的子集，使它们的 gcd（最大公约数）之和最大。
示例数组：{6,7,6,7}.
答案：需要的两个子集是：{6,6}和{7,7}；他们各自的gcd是6和7，他们的sum = 6+7=13；这是可能的最大 gcd 总和。
Gcd: {8,12} 的 Gcd 是 {4} 因为 4 是除 8 和 12 的最大数。
注意：gcd(X)=X 如果子集只包含一个元素。
我的方法：通过暴力破解，找到数组所有可能的子序列，然后找到最大和，但是如果输入大小大于30个数字，这不起作用。我正在寻找更有效的方法。
Extra(s): 任何输入数字的最大大小为 10^9 ，时间限制：-1s 似乎不错，输入大小可能与 10^5
一样大我觉得这其实是一个容易的问题。
首先，让我们忽略值出现不止一次的可能性。显然，最好将一个值的所有副本放在同一个集合中，因为将其中一些副本移到别处只会损害 GCD（edit: 除非只有一个不同的值） .所以我们假设所有元素都是不同的。另外，令 M 为任何元素的最大值。
这样想：有一个简单的解决方案，将最高元素放在一侧，将所有其余元素放在另一侧。 "All the rest" - GCD 可能为 1（当然可能更高），因此此解决方案为您提供 M+1。
具有多个不同元素的任何输入子集的 GCD 都不能高于 M/2（因为这样的除数必须乘以另一个至少为 2 的除数才能得到原始值，不高于 M)。所以 edit: 最优解不能由两个集合组成，每个集合都有多个不同的元素。它必须是一个元素与所有其他元素。
现在考虑 两个 最高元素，其中一些 d 的值为 M 和 M-d。如果我们都不选择它们作为单例，则它们都在 large-group 侧，这意味着该组最多具有 GCD d（因为如果 g|M 和 g|M-d 则 g| d);并且单例的贡献不会超过M-d-1。所以总分最多为 M-1——也就是说，小于我们在选择最高值时得到的分数。 因此，输入中的最高值或 second-highest（不同的）值必须在其自身的集合中。
因此您必须执行以下操作：
- 处理只有一个不同值的琐碎情况。
- 否则，获取最高的2个元素；.
- 计算所有 n-2 个最低元素的 GCD g_0。
- 计算 GCD 的 g_with_highest = GCD(g_0, M) 和 g_with_second_highest = GCD(g_0, M-d).
- 通过比较M + g_with_second_highest和(M-d) + g_with_highest选择单例。