結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2021-10-20 20:48:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 680 bytes |
コンパイル時間 | 3,954 ms |
コンパイル使用メモリ | 250,520 KB |
最終ジャッジ日時 | 2025-01-25 02:03:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 bool check(int n){ if(n==1)return false; for(int i=2;i*i<=n;i++){ if(n%i==0)return false; } return true; } int main(){ int N; cin>>N; vector<int> p; for(int i=2;i<=N;i++){ if(check(i))p.push_back(i); } vector<bool> dp(N+1,false); dp[0] = true; dp[1] = true; for(int i=2;i<=N;i++){ rep(j,p.size()){ if(i-p[j]<0)break; if(dp[i-p[j]]==false){ dp[i] = true; break; } } } cout<<(dp.back()?"Win":"Lose")<<endl; return 0; }