No. of subsets whose gcd is 1

                                         

                           Subtraction Game 2 

                                     https://www.codechef.com/problems/AMSGAME2


                       It is only a branch and bound type of recursion.

1. #include<bits/stdc++.h>
3. using namespace std;
4. long long int n,i;
5. long long int a[1000];
6. long long int dp[70][50010];
7. long long int go(long long int cur_indx,long long int cur_gcd)
8. {
9. if(cur_indx>=n && cur_gcd==1)
10. return 1;
11. else if(cur_indx>=n && cur_gcd!=1)
12. return 0;
14. if(dp[cur_indx][cur_gcd]!=-1)
15. return dp[cur_indx][cur_gcd];
16. else
17. {
18. long long int result=0;
19. result=go(cur_indx+1,cur_gcd); /// without taking a[i];
20. result+=go(cur_indx+1,__gcd(cur_gcd,a[cur_indx])); /// with taking a[i];
21. 
    
22. dp[cur_indx][cur_gcd]=result;
23. return result;
24. }
25. }
28. int main()
29. {
30. int t;
31. cin>>t;
32. while(t--)
33. {
34. // memset(dp,-1,sizeof(dp));
35. for(int i=0;i<70;i++) for(int j=0;j<10005;j++) dp[i][j]=-1;
36. cin>>n;
37. 
    
38. for(i=0;i<n;i++)
39. cin>>a[i];
40. 
    
41. cout<<go(0,0)<<endl;
42. }
43. return 0;
44. }