naoya_t@hatenablog

いわゆるチラシノウラであります

SRM575

Easy ("TheNumberGameDivOne", 250)

  • 1e18までの素因数分解とか無理っしょ
  • 別途シミュレーションしてみて規則性を探る系

シミュレーションコード

vector<bool> sieve;
map<ll,int> mm;

bool solve(ll n) {
  if (found(mm,n)) return mm[n];
  if (n == 1 || sieve[n]) return mm[n]=false;

  vector<ll> q;
  for (ll d=2; d<n; ++d) {
    if (n % d == 0) {
      if (!solve(n-d)) return mm[n]=true;
    }
  }
  return mm[n]=false;
}

int main(int argc, char **argv){
  int M = atoi(argv[1]);

  sieve.assign(M, true);
  sieve[0] = sieve[1] = false;
  for(int i=2; i<M; ++i) {
    if (!sieve[i]) continue;
    for (int j=i*2; j<M; j+=i) {
      sieve[j] = false;
    }
  }

  for (ll n=1LL; n<=M; ++n) {
    mm.clear();
    bool b = solve(n);
    if (n % 2) {
      // odd -> false
      if (b)
        printf("%lld: %d %s\n", n, b, b ? "John" : "Brus"); // never
    } else {
      if (!b)
        printf("%lld: %d %s\n", n, b, b ? "John" : "Brus"); // 2, 8, 32, 128, 512, 2048, ...
    }
  }
  return 0;
}
  • nが奇数の場合:無条件に先手Johnの負け(Brusの勝ち)
  • nが偶数の場合:2^(2k+1) 型の場合はBrus, それ以外の場合はJohnの勝ち

というわけで

#line 2 "TheNumberGameDivOne.cpp"
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
#include <cassert>

using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

class TheNumberGameDivOne {
  bool solve(ll n) {
    if (n % 2) return false;
    set<ll> except;
    for (ll i=2LL; i<=1000000000000000000LL; i<<=2LL) except.insert(i);
    if (found(except, n)) return false;
    return true;
  }
 public:
  string find(long long n) {
    return solve(n) ? "John": "Brus";
  }
};
  • 165.21pt (22'59'')
  • passed system test
  • いぇい