UVa 10637 : Coprimes

問題リンク：http://uva.onlinejudge.org/external/106/10637.html

問題概要：
整数Sをt個のco-primeな値に分割したものを全て出力せよ

解法：
dfsで枝刈りしながら探索した
brute forceな感じが。。。（正しくは素数使ってなんたらららしい）
全探索する過程で、１つ前の値と今決めた値のgcdが1でないならcontinue
ループでは1から今使える値の半分まで見るようにしたら通った

コード：

int S,t;

bool check(int *array)
{
  rep(i,t)REP(j,i+1,t)if(__gcd(array[i],array[j]) != 1)return false;
  return true;
}

void dfs(int remain,int cnt,int *array)
{
  if(cnt >= t)
    {
      if(check(array))
	{
	  rep(i,t)
	    {
	      if(i != 0)printf(" ");
	      printf("%d",array[i]);
	    }
	  puts("");
	}
      return;
    }

  if(cnt == t-1)
    {
      array[cnt] = remain;
      if(cnt != 0 && __gcd(array[cnt-1],remain) != 1)return;
      if(cnt != 0 && array[cnt-1] > remain)return;
      dfs(remain,cnt+1,array);
      return;
    }

  REP(i,1,(remain+1)/2.0)
    {
      int nremain = remain - i;
      if(cnt != 0 && array[cnt-1] > i)continue;
      if(cnt != 0 && __gcd(array[cnt-1],i) != 1)continue;
      array[cnt] = i;
      dfs(nremain,cnt+1,array);
    }

}

int main()
{
  int N,CNT = 1;
  cin >> N;
  while(N--)
    {
      cin >> S >> t;
      cout << "Case " << CNT++ << ":" << endl;
      int array[t];
      dfs(S,0,array);

    }
  return 0;
}