UVa 10036 - Divisibility

// UVa 10036 - Divisibility

#include <iostream>
#include <string.h>
using namespace std;

#define datatype signed long long int

int main() {
	int cases;
	for (cin >> cases; cases; cases--) {
		int n, m;
		cin >> n >> m;
		int a[10000];
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			a[i] = a[i] % m;
			if (a[i] < 0)
				a[i] += m;
		}
		bool T[10001][100];
		memset(T, false, sizeof(T));
		T[0][0] = true;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (T[i][j]) {
					int k = (j + a[i]) % m;
					T[i + 1][k] = true;
					k = (j - a[i] + m) % m;
					T[i + 1][k] = true;
				}
		cout << (T[n][0] ? "Divisible" : "Not divisible") << endl;
	}

	return 0;
}