一些数字之间的最大公约数

Question

一些数字之间的最大公约数

algorithmmathalgebranumber-theory

11

我们有一些非负整数。我们想要找到最大公约数对。实际上，这个最大值比这个对更重要！

例如，如果我们有：

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。

- user182513

（如果有人编辑，请删除标题中的赘余语） - greybeard

7个回答

5

你可以使用欧几里得算法来找到两个数的最大公约数。

while (b != 0) 
{
    int m = a % b;
    a = b;
    b = m;
}
return a;

- Garee

1

我知道这个。但是如果超过两个数呢？我想要这些数字中一对数的最大公约数。例如，如果数字是：2、4、5、10，则答案是5，但是计算每对数的gcd显然不是高效的方法。 - user182513

2

对于超过两个数的情况，可以使用递归公式 gcd(a[1], ..., a[n]) = gcd(gcd(a[1], ..., a[n - 1]), a[n]). - Wildcat

还可能存在其他算法。http://www.springerlink.com/content/gm5wjjcaaxx544w1/ - Wildcat

这将是一个O(n^2)的解决方案。计算每对数字的最大公约数，并保留找到的最高值。我认为答案是要更有效率。 - Ishtar

@kemiisto - 我认为你的算法会返回最小值，而不是最大值。 - kunigami

3

我认为可以优化的地方是：

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

2) 在计算其他组的GCD时，如果您的Euclidean算法循环低于当前最大的GCD，则可以停止该循环。

就我而言，我无法想到一种方法可以在不尝试逐个计算每个配对的情况下找出一对数的最大公约数（并像上面那样进行优化）。

免责声明：我以前从未研究过这个问题，以上内容纯属个人意见。可能有更好的方法，也可能我错了。如果有人愿意讨论我的想法，我很乐意深入探讨。 :)

- Chris

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时做不必要的工作（同时确保不会错过任何东西）。

- Rex Kerr

2

"...但是从最大公约数的角度来看，唯一知道这一点的方法是......"，但我们不必查看它们，因此我们可以击败 O(n log n)。计算最大公约数并不意味着要查看每个公约数。就像有比 O(n log n) 更快的排序算法一样。 - Ishtar

1

@Ishtar - 不幸的是，没有明显的假设会让你比查看每个GCD更好。有一些不完全不合理的假设可能会让你做得更好（例如，列表中数字的最大大小 M 平均不会超过 N^(3/2) ），但这些假设未被说明。对于一般算法，其中列表不是巨大的且数字的大小总体上比列表长度要大得多，我的示例成立。 - Rex Kerr

1

如果算术运算的时间复杂度为O(1)，则可以在O(n)个gcd中检查是否存在两个数字a,b，使得gcd(a,b)!=1。计算所有数字的乘积P，并检查是否存在一个i，使得gcd(P/a_i,a_i) != 1。如果是这样，就对j进行线性搜索，以找到gcd(a_i,a_j) != 1。然而，我不知道如何利用这个技巧来在Theta(n^2)的时间内更快地找到最大公约数。 - sdcvvc

1

在一些限制条件下，例如数组中的数字在给定范围内，比如1-1e7，可以在O(NlogN) / O(MAX * logMAX)的时间复杂度内完成，其中MAX是A中可能的最大值。

受筛法算法启发，在Hackerrank Challenge中遇到过这个问题 -- 在那里它被用于两个数组。请查看他们的编辑。

查找A的最小值和最大值 - O(N)
创建二进制掩码，标记A中出现在给定范围内的元素，以进行O(1)查找；构建O(N)；存储O(MAX_RANGE)。
对于范围(min(A), max(A))中的每个数字a：
对aa = a; aa < max(A); aa += a:
- 如果A中存在aa，则为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

这将节省一些不必要的计算。

- Mircea

这是一个n*n的算法。 - anshul garg

谢谢！确实，仍然是N的平方。 - Mircea

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^2而不是p_j。例如，对于集合3, 5, 15, 25，你会得到25作为答案，而不是5。

然而，你仍然可以使用这个方法快速过滤数字。例如，在上面的情况下，一旦你确定了25，你可以首先用gcd(a_3, a_i)进行穷举搜索来找到真正的最大值5，然后过滤掉小于或等于5的gcd(m/a_i, a_i)，i!=3（在上面的例子中，这将过滤掉所有其他数字）。

为澄清和证明而添加：

要了解为什么这应该起作用，请注意gcd(a_i,a_j)除以gcd(m/a_i,a_i)对所有j!=i都成立。

我们将gcd(m/a_i,a_i)称为g_i，将max(gcd(a_i,a_j),j=1..n,j!=i)称为r_i。我上面所说的是g_i=x_i*r_i，其中x_i是整数。显然r_i <= g_i，因此在n次gcd操作中，我们获得了r_i的一个上界，对于所有的i。

上述说法并不是很明显。让我们深入探讨一下为什么它是正确的： a_i 和 a_j 的最大公约数是两者共同出现的所有质因数的乘积（根据定义）。现在，将 a_j 乘以另一个数 b。a_i 和 b*a_j 的最大公约数要么等于 gcd(a_i, a_j)，要么是它的倍数，因为 b*a_j 包含了 a_j 的所有质因数，以及由 b 贡献的一些额外的质因数，这些质因数也可能包含在 a_i 的因式分解中。实际上，gcd(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对我们来说非常重要：如果x_i为1，则它是最大公约数本身（如果），否则它是一个很好的候选。为了做到这一点，我们进行另外n-1个gcd操作，并明确计算r_i。然后，我们放弃所有小于或等于r_i的g_j作为候选项。如果我们没有其他候选人了，我们就完成了。如果没有，我们选择下一个最大的g_k，并计算r_k。如果r_k <= r_i，我们放弃g_k，并重复使用另一个g_k'。如果r_k > r_i，我们过滤掉剩余的g_j <= r_k，并重复。

我认为可以构造一个数字集合，使得该算法在O(n^2)中运行（如果我们未能过滤掉任何内容），但在随机数字集上，我认为它将快速摆脱大量的候选项。

- vhallac

你对此有证明吗？ - user182513

不是证明，只是一些简单的事实，你可以根据上面的“注意”部分制定算法。我会编辑答案并添加更多细节，解释为什么我认为这样做是可行的。 - vhallac

我编写了一个样例测试程序来查看性能。上述算法确实生成了正确的值，并且在范围为2到10000的1000个随机数中，它执行了1999到13000次gcd操作（而不是暴力方法的999000次）。如果我使用10000个数字，则在19999到315000个gcd操作之间。不过，我没有检查10000组的暴力结果。那太花时间了。 :) - vhallac

@Dysaster：你最初的建议不会是O(n)。n个输入的乘积有Ω(n)位数（假设值的分布是非平凡的），所以你所做的每个n除法本身都是Ω(n)，总共是Ω(n^2)。不过这是一个有趣的启发式方法。 - Steve Jessop

@Steve：我不确定我理解你的意思。我们是在谈论大数算术的性能吗？如果是这样，并且数字确实是每个单词（比如32位），那么你是正确的。乘法将生成一个大约为n个单词的数字。这是一个我没有考虑过的好点。将n个单词的长除法与单个单词的gcd以及这个数字之间的单个单词数字进行计算并不像n个gcd操作那样慢，但它仍然不是O(n)。 - vhallac

@Dysaster：是的，你跟着我了：只要输入不是大多数都是“1”，它们的乘积将有与所有输入相加一样多的数字。同意n大小的除法比n个gcd操作更快。 - Steve Jessop

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

- El Ronnoco

感谢您编写了伪代码，但我认为您说的很明显。我正在寻找更快的解决方案。像O（nlgn）这样的，O（n ^ 2）并不难！ - user182513

是的，我知道这是暴力破解。你在帖子中没有指定任何速度要求 :) - El Ronnoco

是啊！但我要求一个高效的方法！ - user182513

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steve Jessop · Accepted Answer

如果你想要一种替代明显算法的方法，那么假设你的数字在有限范围内，并且你有足够的内存，你可以打败O(N^2)的时间，其中N是值的数量：

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

这告诉你最大公约数，但并不告诉你哪对数产生了它。对于你的示例输入，计算出的数组如下：

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。 - 对于每个输入整数： - 如果它小于等于当前最佳值，则继续。 - 检查它是否在集合中。如果是，则更新当前最佳值为max(当前最佳值, 这个值)，并继续。否则： - 将其添加到集合中 - 重复所有大于当前最佳值的因子。在集合中添加/查找可能是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)。我不知道这是否比欧几里得算法平均更快，但可能是。显然，它会使用更多的内存。