#496. 小码君的除法算式

小码君的除法算式

题目描述

小码君的面前现在有 N 个整数,他需要去计算在这 N 个数中,每相邻两个数之间(即 N-1个位置)添加加号或者减号,然后将最终运算后的值对整数 K 取余,有没有可能存在余数等于0的情况,若有则输出"Divisible",否则输出"Not divisible"。

输入格式

第一行 一个整数t,表示有t组测试数据
接下来每组测试数据是 两个整数 N,K,以空格分开
后面 N 个整数,以换行分开,其中第 i 个整数为 a_i1iN(1 \le i \le N),依次表示给出的这 N 个整数。

输出格式

对于每组测试数据,对应一行输出,若存在余数等于0的情况,则输出"Divisible",否则输出"Not divisible"。

样例

输入样例1

2
4 7
17 5 -21 15
4 5
17 5 -21 15

输出样例1

Divisible
Not divisible

数据范围

对于40%40\%的数据,1t5,2N201K10,100ai1001≤t≤5,2≤N≤20,1≤K≤10,−100≤ai≤100

对于100%100\%的数据,1t10,2N100001K100,1000ai10001≤t≤10,2≤N≤10000,1≤K≤100,−1000≤ai≤1000

提示

C++中对负数取模有一些独特性,和Python的计算方式有些区别

C++: -5 % 3 的结果为 -2

Python: -5 % 3 的结果为 1

这里两种结果均正确,但是在大部分负数取模时需要使用的是正模数,因此可以用 (n%k+k)%k(n\%k + k)\%k 的方式来保证计算结果为正模数