P1356 Divisibility of a Sequence

For any integer sequence, we can insert either the symbol `+` or `-` between every two integers to form an expression, and thus compute its value. For a given integer sequence, we can construct different expressions in this way and obtain different values. If any one of these values is divisible by $k$, we say the sequence is divisible by $k$. Your task is to determine whether a given sequence is divisible by a given number.

This problem has multiple test cases. The first line contains an integer $M$, the number of test cases. For each test case: - The first line contains two integers $n$ and $k$, where $n$ is the number of integers in the sequence. - The second line contains $n$ integers, which form the input sequence $\{a_i\}$.

Output $M$ lines, each corresponding to a test case in the input. If the sequence is divisible by $k$, output `Divisible`; otherwise, output `Not divisible`. There should be no leading or trailing spaces on the line.

Explanation for Sample 1 For the integer sequence $17, 5, -21, 15$, we can construct $8$ expressions: - $17+5+(-21)+15=16$. - $17+5+(-21)-15=-14$. - $17+5-(-21)+15=58$. - $17+5-(-21)-15=28$. - $17-5+(-21)+15=6$. - $17-5+(-21)-15=-24$. - $17-5-(-21)+15=48$. - $17-5-(-21)-15=18$. This sequence is divisible by $7$ ($17+5+(-21)-15=-14$), but not divisible by $5$. Constraints For all test points, it is guaranteed that $1 \le M \le 20$, $1 \le n \le 10^4$, $2 \le k \le 100$, and $\left| a_i \right| \le 10^4$. - $\text{upd 2022.9.27}$: Added one Hack testdata set. - $\text{upd 2023.11.29}$: Added one Hack testdata set. Translated by ChatGPT 5