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