fork(1) download
copy 
  1. #include<iostream>
  2. #include<math.h>
  3.  
  4. using namespace std;
  5.  
  6. long gcd(long a, long b){
  7.     //cout<<a<<" "<<b<<"\t";
  8.     if(b==0){
  9.         return a;
  10.     }
  11.     else{
  12.         return gcd(b, a%b);
  13.     }
  14. }
  15.  
  16.  
  17.  
  18. int main(){
  19.  
  20. int test;
  21. cin>>test;
  22. while(test--){
  23.     int n;
  24.     cin>>n;
  25.  
  26.     long a[n];
  27.     long gcdC = 0;
  28.     for(long i=0;i<n;i++){
  29.  
  30.         cin>>a[i];
  31.  
  32.     }
  33.     long pow_set_size = pow(2, n);
  34.  
  35.     long counter, j;
  36.  
  37.     long subset[n];
  38.     /*Run from counter 000..0 to 111..1*/
  39.  
  40.     long count = 0;
  41.     for(counter = 0; counter < pow_set_size; counter++)
  42.     {
  43.       long size = 0;
  44.       for(j = 0; j < n; j++)
  45.        {
  46.           /* Check if jth bit in the counter is set
  47.              If set then pront jth element from set */
  48.           if(counter & (1<<j))
  49.             subset[size++] = a[j];
  50.        }
  51.        if(size >= 2){
  52.            /*
  53.            cout<<"Set is : ";
  54.            for(long i=0;i<size;i++){
  55.             cout<<subset[i];
  56.            }
  57.            cout<<"\n";
  58.            */
  59.             long gcdC = gcd(subset[0],subset[1]);
  60.             for(long i = 2;i<size;i++){
  61.                 gcdC = gcd(gcdC, subset[i]);
  62.             }
  63.             //cout<<"GCD is :"<<gcdC<<endl;
  64.             if(gcdC == 1){
  65.                 count++;
  66.             }
  67.        }
  68.     }
  69.  
  70.        cout<<count<<endl;
  71.  
  72.  
  73.  
  74.  
  75.  
  76. }
  77. return 0;
  78. }
  79.  
Success #stdin #stdout 0s 2688KB
comments (?)
stdin
copy 
3
4
2 3 5 7
4
3 4 8 16
3
6 10 15
stdout
copy 
11
7
1
https://ideone.com/OF9ewE
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!