找到每个 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，我们知道数组的所有值不可能相同。但是，它们对于所有 K.

modK

请记住 arr[i]%K（对于满足 0=<i<M 的任何 i）不一定是正数。

提出的算法

代码尚未测试

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

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

现在，查找 G = gcd(arrDiff[0],arrDiff[1],...,arrDiff[M-1] 以查找所有有效的 K。您可以使用您想要的任何 gcd 方法，即 Euclidean Algorithm，以便 iteratively/recursively 找到 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;
}

对于上面的示例，这段代码应该在 arrDiff 中为我们提供 16,32 的值。请注意，使用此方法应该会在下一步的 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

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

总结

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

因此，它实际上是您可能需要的算法的组合。可能有更快的方法来完成我上面向您展示的操作，但现在应该可以理解基本算法了。

Answer 2

#include <stdio.h>
int GCD(int a, int b) {
    while(a!=b) {
        if(a>b) a-=b; else b-=a;
    }
    return a;
}
int main()
{
   int n; scanf("%d",&n);
   int a[n],i,j;
   for(i=0;i<n;i++) {
    scanf("%d",&a[i]);
   }
   //finding minimum
  int min=a[0]; for(i=0;i<n;i++) if(min>a[i]) min=a[i];

  //finding differences and storing except minimum
  int diff[n-1]; for(i=0,j=0;i<n;i++) if(a[i]!=min) diff[j++]=a[i]-min;

  // if n is 2, we have only diff[1], otherwise we can follow algo
  int g=(n==2)?diff[0]:GCD(diff[0],diff[1]); for(i=2;i<n-1;i++) g=GCD(g,diff[i]);

  //finding divisors of the final gcd.
  for(i=2;i<=g;i++) if(g%i==0)printf("%d ",i);
return 0;
}

Answer 3

这是我解决问题的代码

#include<bits/stdc++.h>
using namespace std;

void printEqualModNumbers (int arr[], int n) 
{ 
    sort(arr, arr + n);  
    int d = arr[n-1] - arr[0]; 

    vector <int> v; 
    for (int i=2; i*i<=d; i++) 
    { 
        if (d%i == 0) 
        { 
            v.push_back(i); 
            if (i != d/i) 
                v.push_back(d/i); 
        } 
    } 
    for (int i=0; i<v.size(); i++) 
    { 
        int temp = arr[0]%v[i]; 

        int j; 
        for (j=1; j<n; j++) 
            if (arr[j] % v[i] != temp) 
                break; 

        if (j == n) 
            cout << v[i] <<" "; 
    } 
} 

int main(){
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0 ; i < n ; i++)
        cin >> arr[i];

    printEqualModNumbers(arr, n);
}

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

Find every K such that arr[i]%K is equal to for each arr[i]

algorithm

math

greatest-common-divisor

modular-arithmetic

首先，让我们检查给定值。

提出的算法

穿行其中

初始化一个例子`arr`

创建差异数组

计算`G = gcd`

检查示例

总结

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

Find every K such that arr[i]%K is equal to for each arr[i]

algorithm

math

greatest-common-divisor

modular-arithmetic

首先，让我们检查给定值。

提出的算法

穿行其中

初始化一个例子arr

创建差异数组

计算G = gcd

检查示例

总结

初始化一个例子`arr`

计算`G = gcd`