给定一个由 N 个正整数组成的数组 A。
找到最小的正整数 d, st，不存在整数对 (i,j)(1<=i<j<= N)，其中 abs(A_i - A_j) 可被 d 整除。
给定 N 个元素，并假设所有元素都是唯一的，差异的数量可以是：
第 N - 第 1 个、第 N - 第 2 个、...、第 N - 第 (N-1) 个；
第(N-1)个 - 第1个，第(N-1)个 - 第2个，...，第(N-1)个 - 第(N-2)个；
第(N-2)个-第1个、第(N-2)个-第2个、第(N-2)个-第3个、...、第(N-2)个-第(N-3)个；
。
。
。
第二名 - 第一名；
即总共有 N(N-1)/2 个差异。
让整数数组称为：arr。那么，有：
int arr[N];
我不知道如何以比暴力更好的方式解决这个问题，其中绝对存在 O(N^2) 时间复杂度。
但是，似乎更简单的方法是计算两个数字的 gcd，比如说取最小的整数
d = arr[0]
那么是否可以递归计算
gcd(d, arr[i]), i=1,2,3,..., N-1。
但是，我什至不知道它是否正确。
`
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int checked_atoi (const char *from) {
char *endptr= NULL;
long lval= strtol(from, &endptr, 10);
if (*endptr) {
fprintf(stderr, "invalid number '%s'\n", from);
exit(12);
}
else if (lval<INT_MIN || lval>INT_MAX) {
fprintf(stderr, "value '%ld' out of range\n", lval);
exit(13);
}
return (int)lval;
}
int gcd(int a, int b, int c){
if (b==0)
return a;
printf("\n step: %d<> gcd : a: %d, b: %d", c++, a, b);
return gcd(b, a%b, c);
}
int find_smallest_d(int *arr, int N){
int smallest_d = arr[0];
printf("\n find_smallest_d");
for (int i=1; i<N; i++){
smallest_d = gcd(smallest_d, arr[i], 1);
}
return smallest_d;
}
int main(int argc, char *argv[]){
int N=argc-1;
printf("The size of array: %d", N);
int arr[N];
for (int i=0; i<N; ++i) {
arr[i]= checked_atoi(argv[i+1]);
}
printf("The %d values:", N);
for (int i=0; i<N; ++i) {
printf(" %d", arr[i]);
}
printf("\n");
int smallest_d = find_smallest_d(arr, N);
printf("\n smallest value of d is: %d", smallest_d);
}
`
得到的结果表明程序中逻辑的实现可能是错误的，如获取输入：12,23,34,45,56,67；1. 差异abs(arr[i]-arr[j])的唯一值是：
`
1. abs(12-23) = 11,
2. abs(12-34) = 22,
3. abs(12-45) = 33,
4. abs(12-56) = 44,
5. abs(12-67) = 55,
`
因此，gcd应该是11；虽然不清楚是否需要 gcd。
另外，答案应该是：10。