11

我们有一些非负数。我们想找到具有最大 gcd 的对。实际上这个最大值比对更重要！例如，如果我们有：

2 4 5 15

gcd(2,4)=2

gcd(2,5)=1

gcd(2,15)=1

gcd(4,5)=1

gcd(4,15)=1

gcd(5,15)=5

答案是 5。

4

7 回答 7

5

您可以使用欧几里得算法找到两个数字的 GCD。

while (b != 0) 
{
    int m = a % b;
    a = b;
    b = m;
}
return a;
于 2010-09-08T13:23:08.913 回答
4

如果您想要替代显而易见的算法，那么假设您的数字在有界范围内，并且您有足够的内存，您可以击败 O(N^2) 时间，N 是值的数量：

  • 创建一个小整数类型的数组，索引 1 到最大输入。O(1)
  • 对于每个值，增加索引的每个元素的计数，这是数字的一个因素（确保你没有环绕）。上）。
  • 从数组的末尾开始，向后扫描，直到找到 >= 2 的值。O(1)

这会告诉您最大 gcd，但不会告诉您是哪对产生了它。对于您的示例输入，计算数组如下所示：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 2 1 1 2 0 0 0 0 0  0  0  0  0  1

我不知道这对于您必须处理的输入是否实际上更快。涉及的常数因素很大：值的界限以及在该界限内分解值的时间。

您不必分解每个值 - 您可以使用记忆和/或预生成的素数列表。这给了我一个想法，如果你正在记忆分解，你不需要数组：

  • 创建一个空的 int 集和迄今为止的最佳值 1。
  • 对于每个输入整数：
    • 如果它小于或等于迄今为止最好的，继续。
    • 检查它是否在集合中。如果是这样，best-so-far = max(best-so-far, this-value)，继续。如果不：
      • 将其添加到集合中
      • 重复其所有因素（大于迄今为止最好的）。

集合中的添加/查找可能是 O(log N)，尽管这取决于您使用的数据结构。每个值都有 O(f(k)) 因子，其中 k 是最大值，我不记得函数 f 是什么......

你在集合中遇到一个值就完成了它的原因是你找到了一个数字，它是两个输入值的公因数。如果你继续分解，你只会发现更小的数字，这并不有趣。

我不太确定对于较大的因素重复的最佳方法是什么。我认为在实践中您可能必须取得平衡：您不想完全按降序进行，因为生成有序因子很尴尬，但您也不想实际找到所有因子。

即使在 O(N^2) 的领域中，您也可能能够击败欧几里得算法的使用：

完全分解每个数字，将其存储为素数指数序列（例如，2 是 {1}，4 是 {2}，5 是 {0,0,1}，15 是 {0,1,1}） . 然后，您可以通过取每个索引处的最小值并将它们相乘来计算 gcd(a,b)。不知道这是否平均比 Euclid 快，但它可能是。显然它使用了更多的内存。

于 2010-09-08T15:12:23.023 回答
3

我能想到的优化是

1）从两个最大的数字开始，因为它们可能具有最多的质因数，因此可能具有最多的共享质因数（因此 GCD 最高）。

2）在计算其他对的 GCD 时，如果您低于当前最大的 GCD，您可以停止欧几里得算法循环。

在我的脑海中，我想不出一种方法可以在不尝试单独计算每一对的情况下计算出一对中最大的 GCD（并如上所述进行一些优化）。

免责声明：我以前从未看过这个问题，上面的内容不在我的脑海中。可能有更好的方法，我可能错了。如果有人愿意，我很乐意更详细地讨论我的想法。:)

于 2010-09-08T14:34:04.913 回答
1

这个问题一般没有O(n log n)解决办法。事实上，最坏的情况是O(n^2)列表中的项目数量。考虑以下一组数字：

2^20 3^13 5^9 7^2*11^4 7^4*11^3

只有最后两个的 GCD 大于 1，但是通过查看 GCD 知道这一点的唯一方法是尝试每一对并注意到其中一个大于 1。

所以你被无聊的蛮力尝试每对方法所困，也许有几个聪明的优化来避免在你已经找到一个大的 GCD 时做不必要的工作（同时确保你不会错过任何东西）。

于 2010-09-08T14:53:17.123 回答
1

有一些限制，例如数组中的数字在给定范围内，比如 1-1e7，它在 O(NlogN) / O(MAX * logMAX) 中是可行的，其中 MAX 是 A 中的最大可能值。

受到筛算法的启发，并在Hackerrank 挑战赛中遇到了它——它是针对两个数组完成的。检查他们的社论。

  • find min(A) 和 max(A) - O(N)
    创建一个二进制掩码，以标记 A 的哪些元素出现在给定范围内，用于 O(1) 查找；O(N) 构建；O(MAX_RANGE) 存储。
  • 对于范围内的每个数字 a (min(A), max(A))：
    对于 aa = a；aa < 最大值（A）；一个+=一个：
    • 如果 aa 在 A 中，则为 aa 增加一个计数器，并将其与当前的 max_gcd 进行比较，如果计数器 >= 2（即，您有两个可被 aa 整除的数字）；
    • 为每个 GCD 候选存储前两个候选。
    • 也可以忽略小于当前 max_gcd 的元素；

上一个答案：仍然 O(N^2) -- 对数组进行排序；应该消除一些不必要的比较；

max_gcd = 1
# assuming you want pairs of distinct elements.
sort(a) # assume in place
for ii = n - 1: -1 : 0 do
    if a[ii] <= max_gcd
        break
    for jj = ii - 1 : -1 :0 do
        if a[jj] <= max_gcd 
            break
        current_gcd = GCD(a[ii], a[jj])
        if current_gcd > max_gcd:
            max_gcd = current_gcd

这应该可以节省一些不必要的计算。

于 2017-07-18T07:38:25.277 回答
0

伪代码

function getGcdMax(array[])

    arrayUB=upperbound(array)
    if (arrayUB<1)
        error
    pointerA=0
    pointerB=1

    gcdMax=0

    do
        gcdMax=MAX(gcdMax,gcd(array[pointera],array[pointerb]))
        pointerB++
        if (pointerB>arrayUB)
            pointerA++
            pointerB=pointerA+1
    until (pointerB>arrayUB)

    return gcdMax
于 2010-09-08T14:16:10.913 回答
0

有一个解决方案需要 O(n)：

让我们的数字是a_i。首先，计算m=a_0*a_1*a_2*...。对于每个数字 a_i，计算gcd(m/a_i, a_i). 您要查找的数字是这些值中的最大值。

我还没有证明这总是正确的，但在你的例子中，它有效：

m=2*4*5*15=600,

max(gcd(m/2,2), gcd(m/4,4), gcd(m/5,5), gcd(m/15,15))=max(2, 2, 5, 5)=5

注意：这是不正确的。如果该数字a_i有一个p_j重复两次的因子，并且如果另外两个数字也包含该因子p_j，那么您将得到不正确的结果p_j^2insted p_j。例如，对于 set 3, 5, 15, 25，您会得到25答案而不是5。

但是，您仍然可以使用它来快速过滤掉数字。例如，在上述情况下，一旦确定了 25，您可以先对 with 进行穷举搜索a_3=25以gcd(a_3, a_i)找到真正的最大值 ，5然后过滤掉小于gcd(m/a_i, a_i), i!=3或等于5其他）。

为澄清和证明而添加：

gcd(a_i, a_j)要了解为什么这应该起作用，请注意gcd(m/a_i, a_i)所有j!=i.

我们称gcd(m/a_i, a_i)asg_i和max(gcd(a_i, a_j),j=1..n, j!=i)as r_i。我上面说的是g_i=x_i*r_i, 和x_i是一个整数。很明显r_i <= g_i，在gcd 操作中，我们得到了alln的上限。r_ii

上述说法不是很明显。让我们更深入地研究一下它为什么是真的：和的gcda_i是出现在两者中a_j的所有素因子的乘积（根据定义）。现在，乘以另一个数字，。和的 gcd要么等于，要么是它的倍数，因为包含 的所有素因子，以及由 贡献的更多素因子，它们也可能包含在 的因式分解中。事实上，我认为。但我看不到利用它的方法。:)a_ia_ja_jba_ib*a_jgcd(a_i, a_j)b*a_ja_jba_igcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j)

无论如何，在我们的构造中，m/a_i只是计算所有 的乘积的捷径a_j，其中j=1..1, j!=i。结果，gcd(m/a_i, a_i)包含所有gcd(a_i, a_j)作为一个因素。因此，很明显，这些单独的 gcd 结果中的最大值将除以g_i.

现在，g_i我们对最大的特别感兴趣：它要么是最大 gcd 本身（如果x_i是 1），要么是一个很好的候选者。为此，我们执行另一个n-1gcd 操作，并r_i显式计算。然后，我们将所有g_j小于或等于的都r_i作为候选者。如果我们没有任何其他候选人，我们就完成了。如果不是，我们选择下一个最大的g_k，并计算r_k。如果r_k <= r_i，我们放弃g_k，并与另一个重复g_k'。如果r_k > r_i，我们过滤掉剩余的g_j <= r_k，然后重复。

我认为可以构造一个数字集，使该算法在 O(n^2) 中运行（如果我们未能过滤掉任何东西），但在随机数集上，我认为它会很快摆脱大块候选人。

于 2010-09-08T17:15:13.583 回答