 # DP - AMSGAME2 help!

My approach:

dp[i] = number of sub-sequences containing arr[i]

Ans = Sum(dp[i]);

Number of sub-sequences = for all j < i, a new subsequence is added if

1. gcd(arr[i,j]) = 1

2. Extending the subsequences ending at j, if dp[j] > 0

I am getting WA. Where am I going wrong?

``````    int GCD(int m, int n) {
if(m == 0 && n == 0)
return -1;

if(m < 0) m = -m;
if(n < 0) n = -n;

int r;
while(n) {
r = m % n;
m = n;
n = r;
}
return m;
}

int main()
{
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
int t;

cin>>t;

while(t--)
{
int n;

cin >> n;

int *arr = new int[n];

for ( int i = 0 ; i < n; ++i )
cin >> arr[i];

int *dp = new int[n];

dp=0;
long sum = 0;
for( int i = 1 ; i < n ; ++ i)
{
dp[i] = 0;

for( int j = 0; j < i; ++ j)
{
if ( GCD(arr[i],arr[j]) == 1) dp[i]++;
dp[i] += dp[j];
}

sum +=dp[i];
}

cout << sum << endl;
}
}``````

You are just checking whether gcd(a[i],a[j])==1. There might be a possibility that a subset of array is coprime to a[i]. For example refer to the sample test case 3. In that gcd({6,10},{15})=1. So you need to reframe your dp relation.

//