#line 2 "library/src/template.hpp" #include #define rep(i, N) for (int i = 0; i < (N); i++) #define all(x) (x).begin(),(x).end() #define popcount(x) __builtin_popcount(x) using i128=__int128_t; using ll = long long; using ld = long double; using graph = std::vector>; using P = std::pair; constexpr int inf = 1e9; constexpr ll infl = 1e18; constexpr ld eps = 1e-6; const long double pi = acos(-1); constexpr uint64_t MOD = 1e9 + 7; constexpr uint64_t MOD2 = 998244353; constexpr int dx[] = { 1,0,-1,0 }; constexpr int dy[] = { 0,1,0,-1 }; templateconstexpr inline void chmax(T&x,T y){if(xconstexpr inline void chmin(T&x,T y){if(x>y)x=y;} #line 4 "library/src/math/gcd.hpp" namespace kyopro { template constexpr T _gcd(T a, T b) { assert(a >= 0 && b >= 0); if (a == 0 || b == 0) return a + b; int d = std::min(__builtin_ctzll(a), __builtin_ctzll(b)); a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b); while (a != b) { if (a == 0 || b == 0) { return a + b; } if (a > b) { a -= b; a >>= __builtin_ctzll(a); } else { b -= a; b >>= __builtin_ctzll(b); } } return a << d; } template constexpr T ext_gcd(T a, T b, T& x, T& y) { x = 1, y = 0; T nx = 0, ny = 1; while (b) { T q = a / b; std::tie(a, b) = std::pair{b, a % b}; std::tie(x, nx) = std::pair{nx, x - nx * q}; std::tie(y, ny) = std::pair{ny, y - ny * q}; } return a; } }; // namespace kyopro #line 2 "library/src/internal/barrett.hpp" namespace kyopro { namespace internal { /// @brief barrett reduction class barrett { using u32 = uint32_t; using u64 = uint64_t; u64 m; u64 im; public: explicit barrett() = default; explicit barrett(u64 m_) : m(m_), im((u64)(long double)static_cast(-1) / m_ + 1) {} inline u64 get_mod() const { return m; } constexpr u64 reduce(int64_t a) const { if (a < 0) return m - reduce(-a); u64 q = ((__uint128_t)a * im) >> 64; a -= m * q; if (a >= m) a -= m; return a; } constexpr u64 mul(u64 a, u64 b) const { if (a == 0 || b == 0) { return 0; } u64 z = a; z *= b; u64 x = (u64)(((__uint128_t)z * im) >> 64); u32 v = (u32)(z - x * m); if (v >= m) v += m; return v; } }; }; // namespace internal }; // namespace kyopro #line 6 "library/src/internal/type_traits.hpp" namespace kyopro { namespace internal { /// @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8 template struct first_enabled {}; template struct first_enabled, Args...> { using type = T; }; template struct first_enabled, Args...> : first_enabled {}; template struct first_enabled { using type = T; }; template using first_enabled_t = typename first_enabled::type; template struct int_least { static_assert(dgt <= 128, "digit have to be less or equals to 128"); using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if >; }; template struct uint_least { static_assert(dgt <= 128, "digit have to be less or equals to 128"); using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if >; }; template using int_least_t = typename int_least::type; template using uint_least_t = typename uint_least::type; template using double_size_uint_t = uint_least_t<2 * std::numeric_limits::digits>; template using double_size_int_t = int_least_t<2 * std::numeric_limits::digits>; }; // namespace internal }; // namespace kyopro #line 6 "library/src/internal/montgomery.hpp" namespace kyopro { namespace internal { using u32 = uint32_t; using u64 = uint64_t; using i32 = int32_t; using i64 = int64_t; using u128 = __uint128_t; using i128 = __int128_t; /// @brief MontgomeryReduction template class Montgomery { static constexpr int lg = std::numeric_limits::digits; using LargeT = internal::double_size_uint_t; T mod, r, r2, minv; T calc_inv() { T t = 0, res = 0; for (int i = 0; i < lg; i++) { if (~t & 1) { t += mod; res += static_cast(1) << i; } t >>= 1; } return res; } public: Montgomery() = default; constexpr inline T get_mod() { return mod; } constexpr inline int get_lg() { return lg; } void set_mod(const T& m) { assert(m > 0); assert(m & 1); mod = m; r = (-static_cast(mod)) % mod; r2 = (-static_cast(mod)) % mod; minv = calc_inv(); } T reduce(LargeT x) const { u64 res = (x + static_cast(static_cast(x) * minv) * mod) >> lg; if (res >= mod) res -= mod; return res; } inline T generate(LargeT x) { return reduce(x * r2); } inline T mult(T x, T y) { return reduce((LargeT)x * y); } }; }; // namespace internal }; // namespace kyopro #line 6 "library/src/math/dynamic_modint.hpp" namespace kyopro { /// @note mod は32bitじゃないとバグる template class barrett_modint { using u32 = uint32_t; using u64 = uint64_t; using i32 = int32_t; using i64 = int64_t; using br = internal::barrett; static br brt; static u32 mod; u32 v; // value public: static inline void set_mod(u32 mod_) { brt = br(mod_); mod = mod_; } public: explicit constexpr barrett_modint() : v(0) { assert(mod); } // modが決定済みである必要がある explicit constexpr barrett_modint(i64 v_) : v(brt.reduce(v_)) { assert(mod); } u32 val() const { return v; } static u32 get_mod() { return mod; } using mint = barrett_modint; // operators constexpr mint& operator=(i64 r) { v = brt.reduce(r); return (*this); } constexpr mint& operator+=(const mint& r) { v += r.v; if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator-=(const mint& r) { v += mod - r.v; if (v >= mod) { v -= mod; } return (*this); } constexpr mint& operator*=(const mint& r) { v = brt.mul(v, r.v); return (*this); } constexpr mint operator+(const mint& r) const { return mint(*this) += r; } constexpr mint operator-(const mint& r) const { return mint(*this) -= r; } constexpr mint operator*(const mint& r) const { return mint(*this) *= r; } constexpr mint& operator+=(i64 r) { return (*this) += mint(r); } constexpr mint& operator-=(i64 r) { return (*this) -= mint(r); } constexpr mint& operator*=(i64 r) { return (*this) *= mint(r); } friend mint operator+(i64 l, const mint& r) { return mint(l) += r; } friend mint operator+(const mint& l, i64 r) { return mint(l) += r; } friend mint operator-(i64 l, const mint& r) { return mint(l) -= r; } friend mint operator-(const mint& l, i64 r) { return mint(l) -= r; } friend mint operator*(i64 l, const mint& r) { return mint(l) *= r; } friend mint operator*(const mint& l, i64 r) { return mint(l) += r; } friend std::ostream& operator<<(std::ostream& os, const mint& mt) { os << mt.val(); return os; } friend std::istream& operator>>(std::istream& is, mint& mt) { i64 v_; is >> v_; mt = v_; return is; } template mint pow(T e) const { mint res(1), base(*this); while (e) { if (e & 1) { res *= base; } e >>= 1; base *= base; } return res; } inline mint inv() const { return pow(mod - 2); } mint& operator/=(const mint& r) { return (*this) *= r.inv(); } mint operator/(const mint& r) const { return mint(*this) *= r.inv(); } mint& operator/=(i64 r) { return (*this) /= mint(r); } friend mint operator/(const mint& l, i64 r) { return mint(l) /= r; } friend mint operator/(i64 l, const mint& r) { return mint(l) /= r; } }; }; // namespace kyopro template typename kyopro::barrett_modint::u32 kyopro::barrett_modint::mod; template typename kyopro::barrett_modint::br kyopro::barrett_modint::brt; namespace kyopro { template class dynamic_modint { using LargeT = internal::double_size_uint_t; static T mod; static internal::Montgomery mr; public: static void inline set_mod(T mod_) { mr.set_mod(mod_); mod = mod_; } static inline T get_mod() { return mod; } private: T v; public: dynamic_modint(T v_ = 0) { assert(mod); v = mr.generate(v_); } inline T val() const { return mr.reduce(v); } using mint = dynamic_modint; mint& operator+=(const mint& r) { v += r.v; if (v >= mr.get_mod()) { v -= mr.get_mod(); } return (*this); } mint& operator-=(const mint& r) { v += mr.get_mod() - r.v; if (v >= mr.get_mod) { v -= mr.get_mod(); } return (*this); } mint& operator*=(const mint& r) { v = mr.mult(v, r.v); return (*this); } mint operator+(const mint& r) { return mint(*this) += r; } mint operator-(const mint& r) { return mint(*this) -= r; } mint operator*(const mint& r) { return mint(*this) *= r; } mint& operator=(const T& v_) { (*this) = mint(v_); return (*this); } friend std::ostream& operator<<(std::ostream& os, const mint& mt) { os << mt.val(); return os; } friend std::istream& operator>>(std::istream& is, mint& mt) { T v_; is >> v_; mt = v_; return is; } template mint pow(P e) const { assert(e >= 0); mint res(1), base(*this); while (e) { if (e & 1) { res *= base; } e >>= 1; base *= base; } return res; } mint inv() const { return pow(mod - 2); } mint& operator/=(const mint& r) { return (*this) *= r.inv(); } mint operator/(const mint& r) const { return mint(*this) *= r.inv(); } mint& operator/=(T r) { return (*this) /= mint(r); } friend mint operator/(const mint& l, T r) { return mint(l) /= r; } friend mint operator/(T l, const mint& r) { return mint(l) /= r; } }; }; // namespace kyopro template T kyopro::dynamic_modint::mod; template kyopro::internal::Montgomery kyopro::dynamic_modint::mr; /// @brief dynamic modint(動的modint) /// @docs docs/math/dynamic_modint.md #line 3 "library/src/math/miller.hpp" namespace kyopro { namespace miller { using i128 = __int128_t; using u128 = __uint128_t; using u64 = uint64_t; using u32 = uint32_t; template bool inline miller_rabin(u64 n, const u64 bases[], int length) { u64 d = n - 1; while (~d & 1) { d >>= 1; } u64 rev = n - 1; if (mint::get_mod() != n) { mint::set_mod(n); } for (int i = 0; i < length; i++) { u64 a = bases[i]; if (n <= a) { return true; } u64 t = d; mint y = mint(a).pow(t); while (t != n - 1 && y.val() != 1 && y.val() != rev) { y *= y; t <<= 1; } if (y.val() != rev && (~t & 1)) return false; } return true; } constexpr u64 bases_int[3] = {2, 7, 61}; // intだと、2,7,61で十分 constexpr u64 bases_ll[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; /// @brief MillerRabinの素数判定 constexpr bool is_prime(u64 n) { if (n < 2) { return false; } else if (n == 2) { return true; } else if (~n & 1) { return false; } if (n < (1ul << 31)) { return miller_rabin>(n, bases_int, 3); } else { return miller_rabin>(n, bases_ll, 7); } } }; // namespace miller }; // namespace kyopro #line 6 "library/src/math/rho.hpp" namespace kyopro { ///@brief 高速素因数分解(Pollard Rho法) namespace rho { using namespace std; using i128 = __int128_t; using u128 = __uint128_t; using u64 = uint64_t; using u32 = uint32_t; template u64 find_factor(u64 n) { static u64 v = 20001; if (~n & 1uL) { return 2; } if (kyopro::miller::is_prime(n)) { return n; } if (mint::get_mod() != n) { mint::set_mod(n); } while (1) { v ^= v << 13, v ^= v >> 7, v ^= v << 17; u64 c = v; auto f = [&](mint x) -> mint { return x.pow(2) + c; }; v ^= v << 13, v ^= v >> 7, v ^= v << 17; mint x = v; mint y = f(x); u64 d = 1; while (d == 1) { d = _gcd(abs((long long)x.val() - (long long)y.val()), n); x = f(x); y = f(f(y)); } if (1 < d && d < n) { return d; } } exit(0); } template std::vector rho_fact(u64 n) { if (n < 2) { return {}; } if (kyopro::miller::is_prime(n)) { return {n}; } std::vector v; std::vector st{n}; while (st.size()) { u64& m = st.back(); if (kyopro::miller::is_prime(m)) { v.emplace_back(m); st.pop_back(); } else { u64 d = find_factor(m); m /= d; st.emplace_back(d); } } return v; } inline std::vector factorize(u64 n) { if (n < 2) { return {}; } auto v = (n < (1uL << 31) ? rho_fact>(n) : rho_fact>(n)); std::sort(v.begin(), v.end()); return v; } std::vector> exp_factorize(u64 n) { std::vector pf = factorize(n); if (pf.empty()) { return {}; } vector> res; res.emplace_back(pf.front(), 1); for (int i = 1; i < (int)pf.size(); i++) { if (res.back().first == pf[i]) { res.back().second++; } else { res.emplace_back(pf[i], 1); } } return res; } }; // namespace rho }; // namespace kyopro #line 3 "main.cpp" int main(){ int n; scanf("%d", &n); constexpr int NIM_MAX = 30; int grundy[NIM_MAX + 1]; int transit; for (int i = 0; i <= NIM_MAX; i++) { grundy[i] = __builtin_ctz(~transit); transit |= 1 << grundy[i]; } int xor_sum = 0; auto pf = kyopro::rho::exp_factorize(n); for (const auto&[p,e]:pf){ xor_sum ^= grundy[e]; } if (xor_sum) { puts("Alice"); } else { puts("Bob"); } }