// No.7 プライムナンバーゲーム // https://yukicoder.me/problems/no/7 // #include #include #include #include using namespace std; vector create_prime_list(unsigned int limit); vector create_prime_list(unsigned int limit) { // エラトステネスの篩 vector isprime(limit+1, true); isprime[0] = false; isprime[1] = false; for (auto i = 2; i <= sqrt(limit); ++i) { if (isprime[i]) { int j = i + i; while (j <= limit) { isprime[j] = false; j += i; } } } return isprime; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); unsigned int N; cin >> N; // 素数リストの作成 vector res = create_prime_list(N); vector primes; for (auto i = 2; i < res.size(); ++i) { if (res[i]) primes.push_back(i); } // 先攻に必勝パタンがあるか調べる vector lut(N+1, false); for (auto i = 4; i <= N; ++i) { for (auto p: primes) { // 1手進めて負けパタンに持ち込めるのであれば、先手が必勝 if (i-p >= 2 && lut[i-p]==false) { lut[i] = true; break; } } } // 結果の判定と表示 if (lut[N]) cout << "Win" << endl; else cout << "Lose" << endl; }