最大化一个分区的GCD(最大公约数)的总和? [英] Maximize the sum of GCDs (Greatest Common Divisors) of a bipartition?

问题描述

给出一个正数数组.我想将数组拆分为2个不同的子集，以使它们的gcd(最大公约数)的总和最大.

Given an array of positive numbers. I want to split the array into 2 different subset(s) such that the sum of their gcd (greatest common divisor) is maximum.

示例数组: {6,7,6,7} .

答案:两个必需的子集是: {6,6} 和 {7,7} ；它们的gcd分别为6和7，它们的 sum = 6 + 7 = 13 ；这是最大的gcd总和.

Answer: The two required subsets are: {6,6} and {7,7}; their respective gcd(s) are 6 and 7, their sum = 6+7=13; which is the maximum gcd summation possible.

Gcd: {8,12} 的Gcd为 {4} ，因为4是除以8以及12的最大数.

Gcd: Gcd of {8,12} is {4} as 4 is the greatest number which divides 8 as well as 12.

注意:如果子集仅包含一个元素，则 gcd(X)= X .

Note: gcd(X)=X in case the subset contains only one element.

我的方法:通过暴力破解，我找到了数组的所有可能子序列，然后找到了最大和，但是如果输入大小大于30个数字，这将不起作用.我正在寻找一种更有效的方法.

My approach: By brute-forcing, I find all possible sub-sequences of the array,then, I find the maximum sum, but this does not work if the input size is greater than 30 numbers. I am in search of a more efficient approach.

额外:任何输入数字的最大大小为10 ^ 9，时间限制:-1s似乎不错，输入大小可能高达10 ^ 5

Extra(s): Maximum size of any input number is 10^9 , time limit:-1s seems good, size of input might be as huge as 10^5

推荐答案

我认为这实际上是一个容易解决的难题.

I think this is actually an easy problem posing as a difficult one.

首先，让我们忽略值出现多次的可能性.显然，最好将一个值的所有副本放在同一集合中，因为将其中一些副本移动到其他位置只会损害GCD(，除非只有一个不同的值).因此，我们假设所有元素都是不同的.另外，令M为任何元素的最大值.

First, let's ignore the possibility of values appearing more than once. Obviously, it is best to put all copies of a value in the same set, since moving some of them elsewhere can only hurt the GCD (edit: unless there is only a single distinct value). So we'll assume all elements are distinct. Also, let M be the maximum value of any of the elements.

以这种方式思考:有一个简单的解决方案，即在一侧采用最高元素，而在另一侧采用其余元素.所有其他"-的GCD可能为1(当然可能更高)，因此此解决方案可为您提供M + 1.

Think about this way: There's a trivial solution of taking the highest element on one side, and all the rest on the other. "All the rest" - may have a GCD of 1 (could be higher of course), so this solution gives you M+1.

任何具有多个不同元素的输入子集，其GCD都不能高于M/2(因为除数必须乘以另一个除数(至少为2)才能达到原始值，不高于M).因此，编辑:最优解决方案不能由两组分别具有多个不同元素的组组成.它必须是一个元素，而不是所有其他元素.

Any subset of your inputs with more than a single distinct element cannot have a GCD higher than M/2 (since such a divisor has to be multiplied by another divisor, which is at least 2, to get to the original value, which is no higher than M). So edit: an optimal solution cannot be made up of two sets with multiple distinct element each. It must be one element vs all other elements.

现在考虑两个最高元素，对于某些d具有值M和M-d.如果我们都不选择它们作为单例，则它们都在大组一侧，这意味着该组最多具有d的GCD(因为如果g | M和g | M-d则为g | d)；单身人士的贡献将不超过M-d-1.因此，总得分最多为M-1，也就是说，比我们选择最高值时得到的得分要小.因此，在这种情况下，输入中的最高值或第二高(唯一)值必须位于其自己的集合中.

Now consider the two highest elements, having values M and M-d for some d. If we choose neither of them to be the singleton, they're both in the large-group side, which means that group has GCD at most d (since if g|M and g|M-d then g|d); and the contribution of the singleton will be no more than M-d-1. So the overall score would be at most M-1 - that is, less than the score we get when choosing the highest value. It is therefore the case that either the highest or the second-highest (distinct) value in the input must be in a set of its own.

因此，您必须执行以下操作:

You must therefore need to do the following:

• 处理只有一个不同值的琐碎情况.
• 否则，获取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进行比较来选择单例.

这篇关于最大化一个分区的GCD(最大公约数)的总和?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！