2013年3月18日

UVa 10015 - Joseph's Cousin


#include <cstdio>
#include <vector>

int prime[50000], p[9999], N, ans[9999];

int main() {
  prime[0] = prime[1] = 1;
  for (int i = 0; i < 50000; i++)
    if (!prime[i]) {
      p[N++] = i;
      for (int j = i + i; j < 50000; j += i)
        prime[j] = 1;
    }
  int n;
  for (n = 1; n <= 3501; n++) {
    std::vector<int> v;
    for (int i = 1; i <= n; i++)
      v.push_back(i);
    int now = 0, pos = 0;
    while (v.size() > 1) {
      pos = (pos + p[now++] - 1) % v.size();
      v.erase(v.begin() + pos);
    }
    ans[n] = v[0];
  }
  while (scanf("%d", &n) && n)
    printf("%d\n", ans[n]);
  return 0;
}

沒有留言:

張貼留言