给出一个含有n个数字的序列,在这n个数字中间的n-1个位置任意添加加号或者减号
总共有2^(n−1) 种情况,请判断是否存在一种情况使得最后的计算结果可以整除k?
输入有多组数据
每组数据第一行有两个整数n和k(1<=n<=10000, 1<=k<=100)
第二行有n个整数表示给出的序列,每个数字的绝对值小于10000
对于每组数据输出一行
如果存在一种情况使得结果可以整除k,输出“Divisible”(不含引号)
不存在则输出“Not divisible”(不含引号)
样例输入
4 7
17 5 -21 15
4 5
17 5 -21 15
样例输出
Divisible
Not divisible
有哪位大佬能解一下吗,我写的平方阶复杂度的代码过不了
下面是我的代码
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main() {
int n,k;
while(cin>>n>>k) {
map<int,int> p;//存储计算结果
map<int,int> q;
for(int i=-k+1;i<k;i++){
p[i]=0;
}
vector<int> arr;//存储数据
for(int i=0;i<n;i++){
int t;
cin>>t;
if(t%k!=0){
arr.push_back(t%k);
}
}
if(arr.size()==0){
cout<<"Divisible"<<endl;
continue;
}
p[arr[0]]=1;
p[-arr[0]]=1;
for(int i=1;i<arr.size();i++){//逐步更新求得的计算结果
for(int j=-k+1;j<k;j++){
if(p[j]!=0){
q[(j+arr[i])%k]=1;
q[(j-arr[i])%k]=1;
}
}
p.clear();
p=q;
q.clear();
}
if(p[0]==1){
cout<<"Divisible"<<endl;
}
else{
cout<<"Not divisible"<<endl;
}
p.clear();
q.clear();
arr.clear();
}
return 0;
}