Sherlock and Coprime Subset

QUESTION

Recently Watson learned the concept of coprime numbers and now he wonders given an array A1, A2 . . . AN what is the size of the largest subset of the array such that the each pair of elements in the subset is coprime.\n\nWatson asks Sherlock for help and in turn Sherlock needs you.\n\nInput \n\nFirst line contains T, the number of test cases. \nEach test case contains N in one line, number of elements in the array. \nNext line contains N space separated elements A1, A2 . . . AN.\n\nOutput \n\nFor each test case, output the required answer in one line.\n\nConstraints: \n1 <= T <= 10 \n25% test data: 1 <= N <= 10 \n75% test data: 1 <= N <= 50 \n1 <= Ai <= 50.

ANSWER

#include <stdio.h>
#include <string.h>
#define MAX(x,y) (x>y?x:y)
int a[100],b[100];
int dp[60][131072];
int primes[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int bitmask[51];
int N;
int recurr(int idx,int mask){
 if(dp[idx][mask]==-1){
  dp[idx][mask]=0;
  if(idx==N)
   dp[idx][mask]=0;
  else{
   dp[idx][mask] = recurr(idx+1,mask ) ; 
   if((a[idx]&mask)==0)
    dp[idx][mask]=MAX(dp[idx][mask],recurr(idx+1,mask|a[idx])+1);
  }
 }
 return dp[idx][mask];
}
int main()
{
 int t,i,j;
 scanf("%d", &t);
 for(i = 0 ; i < 15 ; i++ )
 {
  bitmask[primes[i]] = i ;
 }
 while(t--)
 {
  scanf("%d", &N);
  for( j = 0 ; j < N ; j++ )
  {
   scanf("%d", &b[j]);
   int x = b[j] ;
   int vv = 0 ;
   for( i = 2 ; i * i <= x ; i++ )
   {   
    if( x % i == 0 )
    {
     vv |= ( 1 << bitmask[i] ) ;
    }
    while( x % i == 0)
    {
     x /= i ;
    }
   }
   if( x > 1 )
     vv |= ( 1 << bitmask[x] ) ;
   a[j] = vv ;
  }
  memset(dp , -1 , sizeof(dp));
  int ans = recurr(0 ,0) ;
  printf("%d\n", ans);
 }
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.