// No.7 プライムナンバーゲーム #include #include using namespace std; int main() { int N; cin >> N; vector isPrime(N + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i <= N; ++i) { if (!isPrime[i]) continue; for (int j = i * 2; j <= N; j += i) { isPrime[j] = false; } } vector primes; for (int i = 1; i <= N; ++i) { if (isPrime[i]) primes.push_back(i); } vector memo(N + 1); vector used(N + 1, false); auto dfs = [&](auto dfs, int n) -> bool { if (n == 0 || n == 1) return true; if (used[n]) return memo[n]; used[n] = true; bool res = false; for (auto p: primes) { if (p > n) break; res = res || !dfs(dfs, n - p); } return memo[n] = res; }; if (dfs(dfs, N)) cout << "Win" << endl; else cout << "Lose" << endl; }