Modular Problem: Mod of a negative number ..llike -16%3 = 2
It is DP problem.
such input of data is in p[]; divident is k;
let , s=a[0]%k;
and s=-a[0]%k;
if any of s <0
then s =s+k [see mod of a negative number]
keep track in 2D array in a[0][s]=1.
s=s+p[1]%k,
for each s check this:
if any of s <0
then s =s+k [see mod of a negative number]
a[1][s]=1 &
s=s-p[1]%k,
a[1][s]=1…and so on
until end of input array
and last if a[last][0] is 1 then divisible else not.
[highlight]Solultion:[/highlight]
#include <iostream>
#include <stdio.h>
//#include <stdlib.h>
#include <fstream>
using namespace std;
int in[10010];
int a[10010][111];
int main()
{
int t,n,k;
int p,f;
cin>>t;
//ofstream out;
//out.open("o.txt");
while(t--)
{
cin>>n>>k;
f=0;
for(int i=0;i<10010;i++)
for(int j=0;j<111;j++)
a[i][j]=-1;
for(int i=0;i<n;i++)
{
cin>>in[i];
if(i==0)
{
p=in[i]%k;
//in[i]=p;
if(p<0)
p=p+k;
a[i][p]=p;
p=-in[i]%k;
if(p<0)
p=p+k;
continue;
}
for(int j=0;j<k;j++)
{
if(a[i-1][j]!=-1)
{
p = (a[i-1][j]+in[i])%k;
if(p<0)
p=p+k;
a[i][p]=p;
if(i==n-1 && p==0)
f=1;
p = (a[i-1][j]-in[i])%k;
if(p<0)
p=p+k;
a[i][p]=p;
if(i==n-1 && p==0)
f=1;
}
}
}
if(n==1)
{
if(abs(in[0])%k==0)
cout<<"Divisible\n";
else
cout<<"Not divisible\n";
continue;
}
if(f)
cout<<"Divisible\n";
else
cout<<"Not divisible\n";
}
//out.close();
return 0;
}