algorithm - gcd的最大总和

Question

有两个自然数数组。有必要使用排列来计算 GCD 的最大总和。

例如：

A = [1,3,5,7,9]
B = [15,20,30,40,50]

我们可以得到 GCD 的最大总和，例如，通过以下混合：

这个测试的答案是 13. (3+3+5+1+1)

数组的长度等于N。并且N可以从 1 到 200。

我试图暴力破解所有组合，但这样的解决方案不符合时间线

请告诉我解决这个问题的算法。

数组中的数字可以是 1 到 10^16。

标签： algorithm

Answer 1

这是我的方法：

1. 首先让我们创建一个加权二分图，数组 A 的元素将属于左侧，数组 B 的元素 - 右侧，并且某些边的权重a->b是gcd(a,b)

2. 现在问题被简化为最优分配问题，可以用各种众所周知的方法来解决，如 Min-Cost-Max-Flow、匈牙利算法等。