2013年8月31日

UVa 10637 - Coprimes

#include <cstdio>

int gcd(int a, int b) {
  while ((a %= b) && (b %= a));
  return a + b;
}

void solve(int s, int t, int last, int now, int * ans) {
  if (!s && now == t) {
    for (int i = 0; i < t; i++) {
      printf("%d%s", ans[i], i == t - 1 ? "\n" : " ");
    }
    return;
  }
  if (!s || now == t) {
    return;
  }
  for (int i = last; i <= s; i++) {
    bool ok = true;
    for (int j = 0; j < now && ok; j++) {
      ok = (gcd(i, ans[j]) == 1);
    }
    if (ok) {
      ans[now] = i;
      solve(s - i, t, i, now + 1, ans);
    }
  }
}

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    printf("Case %d:\n", C++);
    int s, t, ans[99];
    scanf("%d%d", &s, &t);
    solve(s, t, 1, 0, ans);
  }
  return 0;
}

沒有留言:

張貼留言