一些数字之间的最大GCD [英] Greatest GCD between some numbers

问题描述

我们已经有了一些非负数。我们希望找到对最大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＆LT; = 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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！