uva 10036 Problem C: Divisibility

时间:2023-03-08 16:23:03
uva 10036 Problem C: Divisibility

题意:能否在一个整数序列的每相邻的两项之间添加一个加减号,使得最终结果能被一个给定整数K<=100整除。

dp[i][j]表示第i个数取余k为j的布尔值。

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 20000
using namespace std; int t;
int n,k;
int a[maxn];
bool flag;
bool dp[maxn][]; int main()
{
scanf("%d",&t);
while(t--)
{
memset(dp,false,sizeof(dp));
scanf("%d%d",&n,&k);
for(int i=; i<n; i++)
{
scanf("%d",&a[i]);
}
dp[][abs(a[])%k]=true;
for(int i=; i<n; i++)
{
for(int j=; j<k; j++)
{
if(dp[i-][j])
{
dp[i][(j+k+abs(a[i]))%k]=true;
dp[i][((j+k-abs(a[i]))%k+k)%k]=true;
}
}
}
if(dp[n-][]) printf("Divisible\n");
else printf("Not divisible\n");
}
return ;
}