poj Divisibility

POJ Divisibility是一个编程题，要求编写一个程序来确定一系列整数是否可被K整除。输入文件的第一行包含两个整数N和K，用一个空格分隔。第二行包含一系列N个整数，以空格分隔。每个整数的绝对值不大于10000。在输出文件中，如果给定的整数序列可被K整除，则写入单词“Divisible”，否则写入“Not divisible”。

该问题的解决方法可以使用动态规划来实现。我们可以使用一个二维数组dp来记录前i个数产生的余数情况。具体操作如下：
- 初始化dp为1，表示前0个数产生的余数为0。
- 对于每个数a[i]，遍历0到K-1的余数j，如果前i-1个数可以产生余数j，则更新dp[i][(j+a[i])%K]和dp[i][(j-a[i])%K]为1。
- 最后判断dp[N]是否为1，如果是，则输出“Divisible”，否则输出“Not divisible”。

举个例子，对于序列17, 5, -21, 15，根据题目中的描述，可以通过添加加号和减号来得到不同的算术表达式，如17+5-21+15=16，17+5-21-15=-14等。在这个例子中，序列是可被7整除的，因为存在一个算术表达式17+5-21-15=-14的结果可以被7整除，但不可被5整除。

因此，根据题目的描述和动态规划的思想，我们可以编写一个程序来解决POJ Divisibility问题。