#include #include #include #include //自信ないなー。 //なんかうごいてる?? #define Test 0 typedef std::vector PBox; typedef std::map PFType; PBox MakePrime(const std::uint64_t& N) { PBox P(N+1,true); P[0] = false; P[1] = false; for (std::uint64_t i = 2; i <= N; i++) { if (!P[i])continue; for (std::uint64_t j = 2; i*j <= N; j++) { P[i*j] = false; } } return P; } PFType MakePrimeFactor(const std::uint64_t& N,const PBox& PB) { std::uint64_t C = 0; std::uint64_t V = N; PFType PF; for (std::uint64_t i = 0; i <= V; i++) { if (!PB[i]) continue; C = 0; while (V%i == 0) { V /= i; C++; } if(C!= 0) PF[i] = C; } return PF; } bool ErazeZero(PFType& P) { for (PFType::iterator i = P.begin(); i != P.end(); i++) { if (i->second == 0) { PFType::iterator T = i; i--; P.erase(T); if (i == P.end()) break; } } return true; } PFType MakeStuts(PFType& P) { PFType R; std::uint64_t L = 2; for (auto&o : P) { R[o.first] = o.second; if (R[o.first] > L)R[o.first] = L; } return R; } std::uint64_t MustNeedHand(PFType& P) { std::uint64_t R = 0; for (auto&o : P) { R += o.second; } return R; } bool Think(PFType& P) { PFType S = MakeStuts(P); std::uint64_t NH = MustNeedHand(S); std::uint64_t AH = MustNeedHand(P); for (auto&o : P) { if (NH % 2) {//必要ハンド数が奇数の時は・・・。 if (AH % 2) {//必要ハンド数が奇数のときは・・・。 if (o.second > 0) {//カテゴリ消滅 o.second = 0; return true; } }else { if (o.second > 1) {//カテゴリーのラス一残してパス。 o.second = 1; return true; } } } else {//偶数の時 if (o.second > 2) { o.second = 1; } } } for (auto&o : P) {//ここに来るときは各要素1だと思うので、カテゴリ消去を強制する。 o.second = 0; return true; } return false; } bool MakeHoge(const std::uint64_t& N) { std::uint64_t C = 0; PBox PB= MakePrime(N); PFType PF = MakePrimeFactor(N, PB); std::uint64_t V = N; while (PF.size() != 0) { #if Test if (Think(PF) == false) throw 0xDEADBEEF; #else Think(PF); #endif ErazeZero(PF); C++; } return (C%2) != 0; } bool Show(bool F) { std::cout << (F ? "Alice" : "Bob"); return true; } int main() { bool R = false; std::uint64_t N; #if Test N = 4; R = MakeHoge(N); std::cout << N << ':'; Show(R); N = 11; R = MakeHoge(N); std::cout << N << ':'; Show(R); N = 24; R = MakeHoge(N); std::cout << N << ':'; Show(R); N = 600; R = MakeHoge(N); std::cout << N << ':'; Show(R); #else std::cin >> N; R = MakeHoge(N); Show(R); #endif return true; }