本文介绍了一些数字之间的最大GCD的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我们已经有了一些非负数。我们希望找到对最大GCD。其实这是最大的比对更重要!例如,如果我们有:

We've got some nonnegative numbers. We want to find the pair with maximum gcd. actually this maximum is more important than the pair!For example if we have:

2 4 5 15

最大公约数(2,4)= 2

gcd(2,4)=2

GCD(2,5)= 1

gcd(2,5)=1

GCD(2,15)= 1

gcd(2,15)=1

GCD(4,5)= 1

gcd(4,5)=1

GCD(4,15)= 1

gcd(4,15)=1

GCD(5,15)= 5

gcd(5,15)=5

答案是5。

推荐答案

有一个解决方案,将采取为O(n):

There is a solution that would take O(n):

让我们的数字是 A_I 。首先,计算 M = A_0 * A_1 * A_2 * ... 。对于每一个数字A_I,计算 GCD(M / A_I,A_I)。你正在寻找的数字是这些值中的最大值。

Let our numbers be a_i. First, calculate m=a_0*a_1*a_2*.... For each number a_i, calculate gcd(m/a_i, a_i). The number you are looking for is the maximum of these values.

我还没有证明,这始终是正确的,但在你的榜样,它的工作原理:

I haven't proved that this is always true, but in your example, it works:

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 insted的的 p_j 。例如,对于一组 3,5,15,25 ,你得到 25 的答案,而不是 5

NOTE: This is not correct. If the number a_i has a factor p_j repeated twice, and if two other numbers also contain this factor, p_j, then you get the incorrect result p_j^2 insted of p_j. For example, for the set 3, 5, 15, 25, you get 25 as the answer instead of 5.

不过,你仍然可以使用它来快速筛选出号。例如,在上述情况下,一旦你确定了25,你可以先做穷举搜索 A_3 = 25 GCD(A_3,A_I )找到真正的最高, 5 ,然后过滤掉 GCD(M / A_I,A_I),我!= 3 这是小于或等于 5 (在上面的例子中,这个过滤掉所有其他)。

However, you can still use this to quickly filter out numbers. For example, in the above case, once you determine the 25, you can first do the exhaustive search for a_3=25 with gcd(a_3, a_i) to find the real maximum, 5, then filter out gcd(m/a_i, a_i), i!=3 which are less than or equal to 5 (in the example above, this filters out all others).

增加了澄清和说明的:

要明白为什么这应该工作,注意 GCD(A_I,a_j)分歧 GCD(M / A_I,A_I)所有 J 1 = I

To see why this should work, note that gcd(a_i, a_j) divides gcd(m/a_i, a_i) for all j!=i.

让我们把 GCD(M / A_I,A_I) g_i 最大(GCD(A_I,a_j),J = 1 ... N,J!= 1) R_I 。我上面说的是 g_i = x_i * R_I x_i 是一个整数。很明显, R_I< = g_i ,所以在 N gcd操作,以及我们得到了一个上限 R_I 所有

Let's call gcd(m/a_i, a_i) as g_i, and max(gcd(a_i, a_j),j=1..n, j!=i) as r_i. What I say above is g_i=x_i*r_i, and x_i is an integer. It is obvious that r_i <= g_i, so in n gcd operations, we get an upper bound for r_i for all i.

以上要求不是很明显。让我们来看看它深一点,看看它为什么是正确的:的GCD A_I a_j 是所有的产品同时出现在 A_I a_j (顾名思义)主要因素。现在,乘 a_j 其他号码, B 。对 A_I GCD的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),我想。但我看不到的方式来利用这一点。 :)

The above claim is not very obvious. Let's examine it a bit deeper to see why it is true: the gcd of a_i and a_j is the product of all prime factors that appear in both a_i and a_j (by definition). Now, multiply a_j with another number, b. The gcd of a_i and b*a_j is either equal to gcd(a_i, a_j), or is a multiple of it, because b*a_j contains all prime factors of a_j, and some more prime factors contributed by b, which may also be included in the factorization of a_i. In fact, gcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j), I think. But I can't see a way to make use of this. :)

总之,在我们的建筑, M / A_I 简直就是计算所有的产品的快捷方式 a_j ,其中, J = 1..1,J!=我。其结果是, GCD(M / A_I,A_I)包含所有 GCD(A_I,a_j)的一个因素。所以,很显然,这些个人GCD结果的最大将分 g_i

Anyhow, in our construction, m/a_i is simply a shortcut to calculate the product of all a_j, where j=1..1, j!=i. As a result, gcd(m/a_i, a_i) contains all gcd(a_i, a_j) as a factor. So, obviously, the maximum of these individual gcd results will divide g_i.

现在,最大的 g_i 是我们特别感兴趣的:它要么是最大的GCD本身(如 x_i 1),还是一个很好的候选人是之一。为了做到这一点,我们做的另一个 N-1 GCD操作,并计算 R_I 明确。然后,我们放弃所有的 g_j 小于或等于 R_I 作为候选人。如果我们没有任何其它候选左侧,我们已经完成了。如果没有,我们拿起第二大 g_k ,并计算 r_k 。如果 r_k&LT; = R_I ,我们放弃 g_k ,并重复与另一 g_k。如果 r_k&GT; R_I ,我们筛选出剩余的 g_j&LT;。= r_k ,并重复

Now, the largest g_i is of particular interest to us: it is either the maximum gcd itself (if x_i is 1), or a good candidate for being one. To do that, we do another n-1 gcd operations, and calculate r_i explicitly. Then, we drop all g_j less than or equal to r_i as candidates. If we don't have any other candidate left, we are done. If not, we pick up the next largest g_k, and calculate r_k. If r_k <= r_i, we drop g_k, and repeat with another g_k'. If r_k > r_i, we filter out remaining g_j <= r_k, and repeat.

我认为这是可能建立一些组将在O此算法的运行(N ^ 2)(如果我们没有过滤掉任何东西),但随机数套,我认为它会很快摆脱大块的候选人。

I think it is possible to construct a number set that will make this algorithm run in O(n^2) (if we fail to filter out anything), but on random number sets, I think it will quickly get rid of large chunks of candidates.

这篇关于一些数字之间的最大GCD的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

10-11 22:26