c语言 - 确定我们是否可以在数字之间放置'+'和'-'，以便结果可以被数字整除：我的错误在哪里？

Question

我们有howmanynums数字。我们必须确定是否有一种方法可以将'+'和'-'放在它们之间，以使结果可以被给定的数整除 mod .

(最好通过动态编程来完成，但我只是从头开始计算每个序列，因为时间非常短，只需要它才能工作(。

int howmanynums, mod;
int ring(int num) {
    if ((num >= 0) && (num <= mod - 1))
        return num;
    if (num >= mod) {
        while (num >= mod)
            num -= mod;
        return num;
    }
    if (num < 0) {
        while (num < 0)
            num += mod;
        return num;
    }
}
long int p(int n) {
    long int t = 1;
    while (n > 0) {
        t *= 2; 
        n--;
    }
    return t;
}
int sequence[10000][2];
int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%d%d%d", &howmanynums, &mod, &sequence[0][0]);
    sequence[0][0] = ring(sequence[0][0]);
    int temp;
    int k = 1;
    while (k < howmanynums) {
        scanf("%d", &temp);
        sequence[k][0] = ring(temp);
        sequence[k][1] = ring(-temp);
        k++;
    }
    long int x = (p(howmanynums - 1)); 
    while (x > 0) {
        long int a = sequence[0][0];
        long int permutation = x;
        long int insidePermutation = x % 2;
        int l = 1;
        while (l < howmanynums) { 
            a += sequence[l][insidePermutation]; 
            l++; 
            permutation = permutation / 2; 
            insidePermutation = permutation % 2; 
        }
        if (a % mod == 0) {
            printf("%s", "Divisible");
            goto e;
        }
        x--;
    }
     printf("%s", "Not divisible");
 e:
    return 0;
}

它通过了 10 项测试中的 20 项。我不知道测试。

我还尝试将所有整数替换为长整数，但结果相同。

我的错误在哪里？

Answer 1

我简化了你的代码，对我来说看起来还可以。它应该完成这项工作。我唯一关心的是效率。大约需要 20 秒才能找到下一个 30 个数字序列的答案"不可整除"：30 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0每增加一个数字，就会比上一次翻倍。因此，您的代码未通过的测试可能是因为允许的测试时间。

动态编程是通过测试的必要条件。

#include <stdio.h>
#pragma warning(disable : 4996)
int howmanynums, mod, sequence[64];
int main() {
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    scanf("%d%d", &howmanynums, &mod);
    if (howmanynums > 64)
    {
        printf("Too many %d", howmanynums);
    }
    int k = 0;
    while (k < howmanynums)
        scanf("%d", &sequence[k++]);
    int x = (2 << (howmanynums - 2)) - 1;
    bool divisible = false;
    while (!divisible && x >= 0)
    {
        int a = sequence[0], bit = 1;  k = 1;
        while (k < howmanynums)
        {
            a += x & bit ? sequence[k] : -sequence[k];
            k++;
            bit *= 2;
        }
        divisible = a % mod == 0;
        x--;
    }
    printf("%s", divisible ? "Divisible": "Not divisible");
    return 0;
}