結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー 佐藤淳平
提出日時 2019-09-11 23:45:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 8,839 bytes
コンパイル時間 1,745 ms
コンパイル使用メモリ 172,700 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 16:55:25
合計ジャッジ時間 2,222 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using i8   = int8_t; using i16  = int16_t; using i32  = int32_t; using i64  = int64_t;
using u8   = uint8_t; using u16  = uint16_t; using u32  = uint32_t; using u64  = uint64_t;
using f32  = float; using f64  = double;
using vi32  = std::vector<i32>;   using vu32  = std::vector<u32>;   using vf32  = std::vector<f32>;
using vi64  = std::vector<i64>;   using vu64  = std::vector<u64>;   using vf64  = std::vector<f64>;
using vvi32 = std::vector<vi32>;  using vvu32 = std::vector<vu32>;  using vvf32 = std::vector<vf32>;
using vvi64 = std::vector<vi64>;  using vvu64 = std::vector<vu64>;  using vvf64 = std::vector<vf64>;
using pi32  = std::pair<i32,i32>; using pu32  = std::pair<u32,u32>; using pf32  = std::pair<f32,f32>;
using pi64  = std::pair<i64,i64>; using pu64  = std::pair<u64,u64>; using pf64  = std::pair<f64,f64>;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) ((obj).rbegin(),(obj).rend())
#define SZ(obj) ((i32)(obj).size())
#define EACH(it,o) for(auto it=(o).begin();it!=(o).end();++it)
#define IN(l,n,r) ((l)<=(n) && (n)<(r))
#define UNIQUE(obj) (obj).erase(std::unique(ALL(obj)),(obj).end())
#define CLR(ar,val) memset(ar, val, sizeof(ar))
#define FOR(i,a,b) for(i32 i=(i32)(a); i<(i32)(b); i++)
#define RFOR(i,a,b) for(i32 i=(i32)(b)-1;i>=(i32)(a);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define PRINT(n) cout << (n) <<"\n";
#define cauto const auto&
#define mp make_pair
#define pb push_back

const i32 INF   = 0x3F3F3F3F;
const i64 INF64 = 0x3F3F3F3F3F3F3F3F;
const f64 EPS   = 1e-8;
const i32 MOD   = 1000000007;
static const f64 PI     = 3.1415926535897932;
static const f64 NAPIER = 2.7182818284590452;
const char alphabetl[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
const char alphabetu[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
i32 dx[4] = {1, 0, -1, 0};
i32 dy[4] = {0, 1, 0, -1};

template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

i64 BIT_COUNT_ONES(i64 x) {
    return __builtin_popcountll(x);
}
i64 BIT_COUNT_ZEROS(i64 x) {
    return 64 - BIT_COUNT_ONES(x);
}

//gcd(a, b) = a * x + b * y
i64 extgcd(i64 a, i64 b, i64 &x, i64 &y) {
    i64 d = a;
    if(b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}


std::vector<i64> convert_base(i64 x, i64 b) {
    std::vector<i64> ret;
    i64 t = 1, k = abs(b);
    while (x) {
        ret.emplace_back((x * t) % k);
        if (ret.back() < 0) ret.back() += k;
        x -= ret.back() * t;
        x /= k;
        t *= b / k;
    }
    if (ret.empty()) ret.emplace_back(0);
    std::reverse(ALL(ret));
    return ret;
}

std::vector<bool> prime_table(i32 n) {
    std::vector<bool> prime(n + 1, true);
    if(n >= 0) prime[0] = false;
    if(n >= 1) prime[1] = false;
    for(i32 i = 2; i * i <= n; i++) {
        if(!prime[i]) continue;
        for(i32 j = i + i; j <= n; j += i) {
            prime[j] = false;
        }
    }
    return prime;
}

//a ^ x === b (mod p)
i64 mod_log(i64 a, i64 b, i64 p) {
    i64 ok = p, ng = -1;
    while(ok - ng > 1) {
        auto mid = (ok + ng) / 2;
        if (mid * mid >= p) ok = mid;
        else                ng = mid;
    }
    std::unordered_map<i64, i64> baby;
    baby.reserve(ok);
    i64 factor = 1;
    for (i64 i = 0, e = b; i < ok; i++) {
        baby[e] = i;
        (factor *= a) %= p;
        (e *= a) %= p;
    }
    for (i64 i = 1, e = factor; i <= ok; i++) {
        auto it = baby.find(e);
        if (it != baby.end()) return i * ok - it -> second;
        (e *= factor) %= p;
    }
    return -1;
}


//input pair tuple vector
template<typename T1,typename T2> std::istream& operator >> (std::istream& is,std::pair<T1,T2>& p){is>>p.first>>p.second;return is;}
template<typename T1> std::istream& operator >> (std::istream& is,std::tuple<T1>& t){is >> std::get<0>(t);return is;}
template<typename T1,typename T2> std::istream& operator >> (std::istream& is,std::tuple<T1,T2>& t){is >> std::get<0>(t) >> std::get<1>(t);return is;}
template<typename T1,typename T2,typename T3> std::istream& operator >> (std::istream& is,std::tuple<T1,T2,T3>& t){is >>std::get<0>(t)>>std::get<1>(t)>>std::get<2>(t);return is;}
template<typename T1,typename T2,typename T3,typename T4> std::istream& operator >> (std::istream& is,std::tuple<T1,T2,T3,T4>& t){is >> std::get<0>(t)>>std::get<1>(t)>>std::get<2>(t)>>std::get<3>(t);return is;}
template<typename T1,typename T2,typename T3,typename T4,typename T5> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t);return is;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5,T6>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t) >> std::get<5>(t);return is;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6,typename T7> std::istream& operator >> (std::istream& is, const std::tuple<T1,T2,T3,T4,T5,T6,T7>& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t) >> std::get<5>(t) >> std::get<6>(t);return is;}
template<typename T> std::istream& operator >> (std::istream& is,std::vector<T>& as){REP(i,SZ(as))is >>as[i];return is;}

//output set pair map tuple vector
template<typename T> std::ostream& operator << (std::ostream& os, const std::set<T>& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os<<a;}return os;}
template<typename T1,typename T2> std::ostream& operator << (std::ostream& os, const std::pair<T1,T2>& p){os<<p.first<<" "<<p.second;return os;}
template<typename K,typename V> std::ostream& operator << (std::ostream& os, const std::map<K,V>& m){bool isF=true;for(auto& p:m){if(!isF)os<<std::endl;os<<p;isF=false;}return os;}
template<typename T1> std::ostream& operator << (std::ostream& os, const std::tuple<T1>& t){os << std::get<0>(t);return os;}
template<typename T1,typename T2> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2>& t){os << std::get<0>(t)<<" "<<std::get<1>(t);return os;}
template<typename T1,typename T2,typename T3> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5,T6>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t)<<" "<<std::get<5>(t);return os;}
template<typename T1,typename T2,typename T3,typename T4,typename T5,typename T6,typename T7> std::ostream& operator << (std::ostream& os, const std::tuple<T1,T2,T3,T4,T5,T6,T7>& t){os << std::get<0>(t)<<" "<<std::get<1>(t)<<" "<<std::get<2>(t)<<" "<<std::get<3>(t)<<" "<<std::get<4>(t)<<" "<<std::get<5>(t)<<" "<<std::get<6>(t);return os;}
template<typename T> std::ostream& operator << (std::ostream& os, const std::vector<T>& as){REP(i,as.size()){if(i!=0)os<<" "; os<<as[i];}return os;}
template<typename T> std::ostream& operator << (std::ostream& os, const std::vector<std::vector<T>>& as){REP(i,SZ(as)){if(i!=0)os<<std::endl; os<<as[i];}return os;}

void Main();
int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);std::cout<<std::fixed<<std::setprecision(15);Main();return 0;}

void Main() {
    i32 N; cin >> N;
    bool dp[10010];
    dp[0] = dp[1] = true;
    auto prime = prime_table(N);
    vi32 P; 
    for (i32 i = 2; i <= N; i++) if (prime[i]) P.pb(i);

    for (i32 i = 2; i <= N; i++) {
        if (!dp[i]) {
            for (i32 j = 0; j < SZ(P); j++) {
                if (i + P[j] > N) break;
                dp[i+P[j]] = true;
            }
        }
    }
    if (dp[N]) cout << "Win"  << endl;
    else       cout << "Lose" << endl;
}
0