#P1356. 数列的整除性

    ID: 400 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp数论数学福建省历届夏令营

数列的整除性

题目描述

对于任意一个整数数列,我们可以在每两个整数中间任意放一个符号 +-,这样就可以构成一个表达式,也就可以计算出表达式的值。对于一个整数数列来说,我们能通过如上的方法构造出不同的表达式,从而得到不同的数值,如果其中某一个数值能够被 kk 整除的话,我们就称该数列能被 kk 整除。现在你的任务是判断某个数列是否能被某数整除。

输入格式

本题有多组数据

第一行一个整数 MM,表示数据组数。

对于每组数据:

第一行两个整数 nnkknn 表示数列中整数的个数。

第二行 nn 个整数,表示输入数列 {an}\{a_n\}

输出格式

输出应有 MM 行,依次对应输入文件中的 MM 个子任务,若数列能被 kk 整除则输出 Divisible,否则输出 Not divisible ,行首行末应没有空格。

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

Divisible
Not divisible


提示

样例输入输出 1 解释

对于整数数列:17,5,21,1517,5,-21,-15,可以构造出 88 个表达式:

  • 17+5+(21)+15=1617+5+(-21)+15=16
  • 17+5+(21)15=1417+5+(-21)-15=-14
  • 17+5(21)+15=5817+5-(-21)+15=58
  • 17+5(21)15=2817+5-(-21)-15=28
  • 175+(21)+15=617-5+(-21)+15=6
  • 175+(21)15=2417-5+(-21)-15=-24
  • 175(21)+15=4817-5-(-21)+15=48
  • 175(21)15=1817-5-(-21)-15=18

该数列能被 77 整除(17+5+(21)15=1417+5+(-21)-15=-14),但不能被 55 整除。

数据规模与约定

对于全部的测试点,保证 $1 \le n \le 10^4,2 \le k \le 100,\left| a_i \right| \le 10^4$。

  • upd 2022.9.27\text{upd 2022.9.27}:新增加一组 Hack 数据。