找到每个 K 使得 arr[i]%K 等于每个 arr[i]

Question

我有一个由 M 个整数组成的数组。我必须找到所有可能的整数 K（假设至少有 1 K），使得：

1) K > 1
2) arr[0]%K = arr[1]%K = arr[2]%K = ... = arr[M-1]%K 

这个问题的最佳算法是什么？

Answer 1

首先，让我们检查给定。

• 由于存在至少一个K，我们知道，例如，该阵列arr这样arr[0]=4; arr[1]=6; arr[2]=9 是无效的，因为没有模量给出了每个相同的结果。
• 鉴于K> 1，我们知道数组的所有值不能相同。然而，它们modK对所有人都是一样的K。

请记住，arr[i]%K（对于任何这样的我0=<i<M）不必是积极的。

提议的算法

代码没有经过测试

在我看来，确定K值的最简单方法是找出数组中每个值之间的差异。（我将用 Java 展示示例。）假设arrDiff包含每个值的差异，使得

arrDiff[0] = arr[0]-arr[1];
arrDiff[1] = arr[1] - arr[2];
...
arrDiff[M-1] = arr[M-1] - arr[0];

现在， findG = gcd(arrDiff[0],arrDiff[1],...,arrDiff[M-1]找到所有有效的K. 您可以使用任何gcd您想要的方法，即欧几里得算法，以便迭代/递归地找到 G. 您也可以忽略负面差异，因为gcd这会给您带来积极的结果。

[All of G's factors]>1（包括G其本身）将是有效值K。

走过它

我不打算做一个证明（我会把它留给你），但让我们做一个例子来清楚。

初始化示例 arr

//Let's do an easy one with M=3
int arr[] = new int[3];
arr[0] = -7;
arr[1] = 9;
arr[2] = 25

创建差异数组

我将在这里展示一个稍微更有效的实现（感谢@RBarryYoung）。

int min = findSmallestNumber(arr); //Returns min value (may be negative)
//The array size is intended to not include the minimum, assuming we have no duplicates.
int arrDiff[] = new int[arr.length-1];
for(int num : arr){
    if(num==min) continue; 
    arrDiff[num] = arr[num] - min;
}

对于上面的例子，这段代码应该给我们16,32in 的值arrDiff。请注意，使用此方法应该会导致下一步中 gcd 计算的所有正值。

计算 G = gcd

我不打算为您编写 gcd 方法，因为有很多实现；我假设你有一个方法int gcd(int a, int b)。

int g = gcd(arrDiff[0], arrDiff[1]);
for(int i = 2, i < arrDiff.length-1, i++){
    g = gcd(g, arrDiff[i]);
}
//return g; 

请注意，如果数组中只有两个值，则无需gcd使用——只需使用单个差异即可。

检查示例

对于我们的示例，您可以轻松找到 gcd(-16,-16,32)=gcd(16,16,32)=16。因此，16 及其所有因子 >1 应该是答案。让我们至少检查 16。请注意，下面的“=”实际上应该是一个全等符号（三个小节而不是两个小节）。

-7mod16 = 9mod16

9mod16 = 9mod16

25mod16 = 9mod16

您可以检查这是否也适用于 factor 2,4,8。（对于所有这些因素，您应该得到1mod8 => 1mod4 => 1mod2。）

包起来

如果您必须在代码中找到因子，您可能会对各种因子分解算法中的一种感兴趣，以找到G大于 1 的所有因子。选择最优化的可能取决于您的数据。

因此，它实际上是您可能需要的算法组合。可能有稍微快一点的方法来做我上面向你展示的，但基本算法现在应该是平易近人的。