#include #include #include #include #include // 割れた数, 商 std::pair factor_imp(int n) { int max{std::sqrt(n)}; for(int i{2}; i < max + 1; ++i) { if(n % i == 0) { return std::make_pair(i, n / i); } } return std::make_pair(n, 1); } // <素因数, 羃> std::map factor(int n) { std::map map; do { auto v = factor_imp(n); ++map[v.first]; n = v.second; } while(n != 1); return map; } // 奇数個の素数の積を渡されると勝ち。 // 偶数個なら負け。 // 1つだけn次、あとは全部1次のものを渡されると、勝ち。 // n次のものが偶数個だと負け、奇数なら勝ち? int main(int, char**) { int N; std::cin >> N; auto map = factor(N); int count1{}; int count2p{}; for(auto e: map) { if(e.second == 1) ++count1; if(e.second > 1) ++count2p; // std::cout << e.first << ": " << e.second << std::endl; } if(count2p == 0) { std::cout << ((count1 % 2) ? "Alice" : "Bob") << std::endl; } else if(count2p % 2 == 0) { std::cout << "Bob" << std::endl; } else { std::cout << "Alice" << std::endl; } return 0; }