解いた問題

10/27/2011

UVa12218

UVa12218
全部試す。
// UVa12218
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cstring>

using namespace std;

int main(void)
{
  const int P = 9999999 + 1;
  static bool prime[P];
  fill(prime, prime + P, true);
  prime[0] = prime[1] = false;
  for (int i = 2; i * i < P; ++i) {
    for (int j = 2; i * j < P; ++j) {
      prime[i * j] = false;
    }
  }

  int tc;
  char s[10];
  char t[10];
  scanf("%d\n", &tc);
  while (tc--) {
    set<int> vis;
    gets(s);
    const int s_size = strlen(s);
    sort(s, s + s_size);
    for (int bit = 0; bit < (1 << s_size); ++bit) {     
      int t_size = 0;
      for (int i = 0; i < s_size; ++i) {
        if (bit & (1 << i)) t[t_size++] = s[i];
      }
      t[t_size] = '\0';
      do {
        int num = atoi(t);
        if (!prime[num]) continue;
        if (vis.count(num)) continue;
        vis.insert(num);
      } while (next_permutation(t, t + t_size)) ;
    }

    printf("%d\n", vis.size());
  }
  return 0;
}

0 件のコメント :

コメントを投稿