15-2

//главное, что используется в задаче: (a + b) mod n = ((a mod n) + (b mod n)) mod n
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <stdlib.h>

int dp[100001][100], remainders[10000]; //массив, в котором отмечаем "ходы", и массив остатков соответственно

int divisibility(int n, int k, int i, int sum) {
    int plus, minus, t;
    sum = (sum % k + k) % k; //берем остаток от деления очередной суммы; замечание, про которое я говорил: мы пишем (sum % k + k) % k, а не просто sum % k, чтобы остаток всегда был неотрицательный, и это существенно, иначе будет неправильно работать.(В си нет стандарта на неотрицательный остаток. Так, -20 % 9 == -2, а нам надо, чтобы было 7.)
    if (i == n) {
        if (sum == 0) return 1;
        return 0;
    } //i == n значит, что все элементы последовательности были пройдены и добавлены в сумму с тем или иным знаком
    if (dp[i][sum] != -1) return dp[i][sum]; //здесь проверяем, была ли раньше посчитана дальнейшая сумма; если была, то из рекурсии выходим на шаг назад
    plus = divisibility(n, k, i + 1, sum + remainders[i]); //пробуем плюс
    minus = divisibility(n, k, i + 1, sum - remainders[i]); //пробуем минус
    t = (plus | minus);
    dp[i][sum] = t; //запоминаем, что уже посчитали какой-то случай в рекурсии
    return t;
} //итого: функция вернет 1, если последовательность остатков делится на k, 0 - иначе

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int i, j, t, n, k;
    i = 0;
    scanf("%d %d", &n, &k);
    for (i = 0; i < n; i++) {
        for (j = 0; j < k; j++) dp[i][j] = -1;
    }
    i = 0;
    while (scanf("%d", &t) != EOF) {
        if (t % k != 0) {
            remainders[i] = t % k;
            i++;
        }
    } //немного облегчим задачу: будем искать делимость не изначальной последовательности, а последовательности из остатков(можно, в общем-то, делать то же самое с обычной последовательностью)
    if (i == 0) printf("Divisible");
    else if (i == 1) printf("Not divisible"); //два тривиальных случая, когда на вход подается только одно число
    else (divisibility(i, k, 1, remainders[0]) ? printf("Divisible") : printf("Not divisible")); //на вход в функцию подаем: i - количество остатков, k - число, деление на которое проверяем, 1 - номер первого шага, remainders[0] - первая сумма
}