最大公约数和最大值

Question

你将得到两个包含n个元素的数组A和B。选择一对元素(x,y)，使得： • x属于数组A • y属于数组B • GCD(x,y)是所有(x,y)对中最大的。 如果存在多个具有最大GCD的这样的对，则选择具有最大和的那个。打印出该最大和对的元素之和。这是来自Hackerrank weekofcode 34的问题。

from fractions import gcd

from itertools import product
n = int(input().strip()) #two arrays of equal length
A = set(map(int, input().strip().split(' '))) #array1
B = set(map(int, input().strip().split(' '))) # arry2
output_sum=[]
output_GCD=[]
c=list(product(A,B))
for i in c:

    temp1=i[0]
    temp2=i[1]

    sum_two=temp1+temp2

    temp3=gcd(temp1,temp2)
    output_GCD.append(temp3)
    output_sum.append(temp1+temp2)
temp=[]
for i in range(len(output_GCD)):
  if(output_GCD[i]==max(output_GCD)):
    temp.append(output_sum[i])
print(max(temp))

这个解决方案适用于较小的条件，但在大多数测试用例中超时了，请帮助我改进我的解决方案。

- Agastya Teja

---

不确定这是否更快，但是与为每对计算GCD（O（n²））相比，也许只需计算A中所有数字的所有除数，将它们存储在映射中{divisor -> [numbers]}，然后对于B中的所有数字，再次计算所有除数并获取已经在映射中的最大值。 - tobias_k

你可以在每个数组内根据除法丢弃非最大元素，以减少比较次数。 - hilberts_drinking_problem

Answer 1

您可以通过以下方式计算数组A的所有除数a_divisors:

# it is not real python-code, just ideas of algorithm
count = {}
for (i : A): 
  count[i]++

a_divisors = {}
for (i : range(1, 10^6)):
  for (j = i * i; j <= 10^6; j += i):
    if j in count.keys():
      a_divisors[i] = 1

在您可以为B构建相同的数组b_divisors之后，从两个数组中选择公共的最大值。

例如：

5
3 1 4 2 8
5 2 12 8 3

生成因数数组：

a: 1, 2, 3, 4, 8
b: 1, 2, 3, 4, 5, 6, 8, 12

常见的最大值为：4

如果你知道 gcd(a, b) = 4，那么你只需要从 A 中选择一个具有除数 4 的最大值和从 B 中选择一个最大值：8 + 12 = 16

- knst

---

第二部分看起来还不错，但我相信有比测试所有数字到某个任意上限更有效确定所有除数的方法。 - tobias_k

没有除法操作，加减乘速度非常快，但 Key-Map 不够快。首先，我认为将 Key-Map 替换为具有10^6掩码长度的数组会显着提高速度。第二个想法是在第一个范围循环中使用 sqrt(10^6) = 10^3，并添加 a_divisor[j / i ] 和 a_divisor[i] - knst

没有除法，但仍有非常多的测试。如果其中一个数组中最大的数字是10^100，你会仍然使用10^6作为上限吗？还是测试所有小于10^100的数字？ - tobias_k

tobias_k，保证每个A[i]和B[i]都不大于10^6。 - knst

Answer 2

你必须将A和B转换为Set（以便于在其中轻松查找）

def maximumGcdAndSum(A, B):
    A = set(A)
    B = set(B)
    max_nbr = max(max(A), max(B))
    i = max_nbr

    while i > 0:  # for each i starting from max number
        i_pow = i  # i, i^2, i^3, i^4, ...
        maxa = maxb = 0

        while i_pow <= max_nbr:  # '<=' is a must here
            if i_pow in A:
                maxa = i_pow  # get the max from power list which devides A
            if i_pow in B:
                maxb = i_pow  # get the max from power list which devides B
            i_pow += i
        if maxa and maxb:
            return maxa + maxb  # if both found, stop algorithm
        i -= 1

    return 0

- Gurgen Hovhannisyan