Can anyone help me with the below problem : -
The chef was playing a fun event where he was given a number of cards N labelled with an integer on each card and it is represented in an array A . He had to drop them in two baskets, without leaving any empty such that gcd of the integers on the card is one.
If the basket has more than one card, the product of the integers in each card is taken as a parameter for gcd of two integers from the two baskets. Find the number of possible results to drop the cards in the basket such that the gcd(p,q)=1 , where p and q are non-empty subsets which are being split from the array A .
I tried DP but it shows the wrong answer !!
Link : FUN_GAME
Example Input
2
3
2 3 1
4
2 3 6 1
Example Output
6
2
Explanation
For the 1st test case, the following partitions are possible
{1}, {2, 3} = gcd(1,6) = 1
{1, 2}, {3} = gcd(2,3) = 1
{1, 3}, {2} = gcd(3,6) = 1
{2, 3}, {1} = gcd(6,1) = 1
{3}, {1, 2} = gcd(3,2) = 1
{2}, {1, 3} = gcd(2,3) = 1
For the 2nd test case, the following partitions are possible
{1},{2,3,6}=gcd(1,36)=1
{2,3,6},{1}=gcd(36,1)=1