我们有一些非负整数。我们想要找到最大公约数对。实际上,这个最大值比这个对更重要!
例如,如果我们有:
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。
我们有一些非负整数。我们想要找到最大公约数对。实际上,这个最大值比这个对更重要!
例如,如果我们有:
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。
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
M
。第二步的复杂度为O(N*M)
。因此,只有在您的列表相对于您在范围内拥有的整数数量很长时,这才是一个好主意。但这意味着必须重复相同的数字,您最好使用基数排序并查找重复项(O(N+M)
)! - Rex Kerrlog(M)
时间,我猜第二步的复杂度是O(N*M)
而不是O(N*N*log(M))
,因此当M/log(M) < N
时,这是一个很好的策略。 - Rex Kerrk
的因子数量受到2*sqrt(k)
的限制(不确定是否严格)。 - kunigamithis-value
:不需要使用max()
。 - greybeardwhile (b != 0)
{
int m = a % b;
a = b;
b = m;
}
return a;
一般情况下,这个问题没有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时做不必要的工作(同时确保不会错过任何东西)。
O(n log n)
。计算最大公约数并不意味着要查看每个公约数。就像有比 O(n log n)
更快的排序算法一样。 - IshtarM
平均不会超过 N^(3/2)
),但这些假设未被说明。对于一般算法,其中列表不是巨大的且数字的大小总体上比列表长度要大得多,我的示例成立。 - Rex Kerrgcd(a,b)!=1
。计算所有数字的乘积P,并检查是否存在一个i,使得gcd(P/a_i,a_i)
!= 1。如果是这样,就对j
进行线性搜索,以找到gcd(a_i,a_j) != 1
。然而,我不知道如何利用这个技巧来在Theta(n^2)的时间内更快地找到最大公约数。 - sdcvvc在一些限制条件下,例如数组中的数字在给定范围内,比如1-1e7,可以在O(NlogN) / O(MAX * logMAX)的时间复杂度内完成,其中MAX是A中可能的最大值。
受筛法算法启发,在Hackerrank Challenge中遇到过这个问题 -- 在那里它被用于两个数组。请查看他们的编辑。
之前的答案: 仍然是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
有一个解决方案可以在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
,并重复。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