DP - AMSGAME2 help!

general
,
1

Problem Link: http://www.codechef.com/problems/AMSGAME2

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

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.