Problem Link: http://www.codechef.com/problems/AMSGAME2
My approach:
dp[i] = number of subsequences containing arr[i]
Ans = Sum(dp[i]);
Number of subsequences = for all j < i, a new subsequence is added if

gcd(arr[i,j]) = 1

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]=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;
}
}