最大Gcd和总和

Question

您将获得两个分别包含n个元素的数组A和B。选择一对元素（x，y），以便：•x属于数组A•y属于数组B•GCD（x，y）是所有对（x，y）的最大值。如果一对以上具有最大gcd的那对，则选择一个具有最大总和的对。打印此最大和对的元素之和。

这是来自Hackerrankweekofcode34的问题。

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))

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

Answer 1

您可以通过以下方法为数组a_divisors计算所有除数A：

# 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_divisors构造相同的数组B并从两个数组中选择共同的最大值之后

例如：

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中选择1个最大值，从B中选择1个最大值：8 + 12 = 16

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