如何检查整数是否是数组中元素的线性组合？

Question

如何检查一个整数是否可以表示为给定长度为n的数组中元素的线性组合？目前我可以针对 n=2 的特定情况进行编码，但是当 n 未知时我不知道如何编码。

这是n=2时的函数（数组只有两个元素时）：

bool check(int array[], int n, int value){//n values in the array //    

  for (int i=1; i<array[0]; i++){
     for (int j=1; j<array[1]; j++){
        if ((i*array[0]+j*array[1])%value==0){
            printf("x=%d, y=%d, i=%d, j=%d\n", array[0], array[1], i, j);
            return 1;
        }
    }
    }
return 0;
}

Answer 1

我记得在第一年的离散数学课程中，n 是 x 和 y 的线性组合当且仅当 n 是 [=14 的倍数=]（即如果 value % gcd(x,y) == 0）

您可以将此概念用作代码中的强大资产。

这里的寓意是计算集合中所有元素之间的 gcd，并不断检查 value 是否可以被 gcd(x,y) 整除。如果是，则 return 1，否则 0.

我将 gcd() 函数的实现留给您（网上有很多示例），但您可以通过以下方式将其合并到现有代码中：

bool check(int array[], int n, int value){
    for (int i = 0; i < n - 1; i++) {            // notice we only iterate up to n - 1
        for (int j = i + 1; j < n; j++) {
            if (value % gcd(array[i], array[j]) == 0) {
               printf("x=%d, y=%d, i=%d, j=%d\n", array[0], array[1], i, j);
               return 1;
            }
        }  
    }
    return 0;
}

如何检查整数是否是数组中元素的线性组合？

How to check if an integer is linear combination of elements in an array?

c

arrays

boolean

nested-loops