11 algorithm math algebra number-theory
我们有一些非负数.我们希望找到最大gcd对.实际上这个最大值比这对更重要!例如,如果我们有:
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.
您可以使用欧几里德算法来查找两个数字的GCD.
while (b != 0)
{
int m = a % b;
a = b;
b = m;
}
return a;
如果您想要替代明显的算法，那么假设您的数字在有界范围内，并且您有足够的内存，您可以击败 O(N^2) 时间，N 是值的数量：
它告诉你最大 gcd，但不会告诉你哪对产生了它。对于您的示例输入，计算出的数组如下所示：
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
我不知道这对于您必须处理的输入来说是否实际上更快。涉及的常数因素很大：值的界限以及在该界限内分解值的时间。
您不必对每个值进行因式分解 - 您可以使用记忆和/或预先生成的素数列表。这给了我这样的想法：如果你要记住因式分解，则不需要数组：
在集合中添加/查找可能是 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)。不知道这是否平均比欧几里得更快，但可能是。显然它使用了加载更多的内存。
有一个解决方案需要 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，您可以首先对 进行穷举搜索，a_3=25以gcd(a_3, a_i)找到真正的最大值 ，5然后过滤掉gcd(m/a_i, a_i), i!=3小于或等于的5（在上面的示例中，这会过滤掉所有其他的）。
添加用于澄清和论证：
要了解为什么这应该有效，请注意对所有人gcd(a_i, a_j)进行除法。gcd(m/a_i, a_i)j!=i
我们称之为gcd(m/a_i, a_i)asg_i和max(gcd(a_i, a_j),j=1..n, j!=i)as r_i。我上面说的是g_i=x_i*r_i，x_i是一个整数。很明显r_i <= g_i，因此在gcd 运算中，我们得到了所有 的n上限。r_ii
上述说法并不是很明显。让我们更深入地研究一下，看看为什么它是正确的： 和 的 gcda_i是出现在和a_j中的所有素因子的乘积（根据定义）。现在，乘以另一个数字。和的 gcd要么等于，要么是它的倍数，因为包含 的所有素因数，以及 贡献的更多素因数，它们也可能包含在 的因式分解中。事实上，我认为。但我看不出有什么办法可以利用它。:)a_ia_ja_jba_ib*a_jgcd(a_i, a_j)b*a_ja_jba_igcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j)
无论如何，在我们的构造中，m/a_i这只是计算所有a_j, where的乘积的捷径j=1..1, j!=i。结果，gcd(m/a_i, a_i)包含所有gcd(a_i, a_j)作为一个因素。因此，显然，这些单独的 gcd 结果的最大值将除以g_i。
现在，我们特别感兴趣的是最大的g_i：它要么是最大 gcd 本身（如果x_i是 1），要么是一个很好的候选者。为此，我们执行另一个n-1gcd 操作并r_i显式计算。然后，我们放弃所有g_j小于或等于的r_i候选者。如果我们没有其他候选人了，我们就完成了。如果不是，我们选取下一个最大的g_k，并计算r_k。如果r_k <= r_i，我们放弃g_k，并与另一个重复g_k'。如果r_k > r_i，我们过滤掉剩余的g_j <= r_k，然后重复。
我认为可以构造一个数字集，使该算法在 O(n^2) 内运行（如果我们未能过滤掉任何内容），但在随机数字集上，我认为它将很快摆脱大块的候选人。