算法提高之分成互质组

算法提高之分成互质组

• 核心思想：dfs

  
  （图片来源网络，侵删）
  • 枚举每一组可以放哪些元素

  •   #inClude 
      #include 
      #include 
      
      using NAMEspace std;
      const int N = 10;
      int n;
      int a[N];
      int g[N][N];
      int ans = N;
      bool st[N];
      
      int gcd(int a,int b)  //有没有质因数
      {
          return b?gcd(b,a%b):a;
      }
      bool check(int g[],int x,int start)
      {
          for(int i=0;i
              if(gcd(g[i],x)  1) return false;  //如果线性相关
          }
          return true;
      }
      //当前遍历到哪个组;当前组中该放哪个位置;原数组中从哪个位置开始遍历;已经放好的元素个数
      void dfs(int gr,int gc,int start,int cnt)  
      {
          if(gr >;= ans) return;  //不是更优解
          if(cnt == n) ans = min(ans,gr);
          
          bool flag = true;  //记录当前元素(start)是否能放到某一个组中 能放就不开新组
          
          for(int i=start;i
              if(!st[i] && check(g[gr],a[i],gc))  //没用过并且可以放
              {
                  st[i] = true;
                  g[gr][gc] = a[i];  //放到gc处
                  dfs(gr,gc+1,i+1,cnt+1); 
                  st[i] = false;  //回溯
                  flag = false;  //可以放到某个组中
              }
          }
          if(flag) dfs(gr+1,0,0,cnt);  //如果不能放到任何一个组中 开一个新组 同时从0遍历所有元素
      }
      int main()
      {
          cin>n;
          for(int i=0;i>a[i];
          dfs(1,0,0,0);
          
          cout