#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define SAFE_DELETE(p) { delete (p); (p) = nullptr; } #define SAFE_DELETE_ARRAY(p) { delete[] (p); (p) = nullptr; } using namespace std; namespace ValLib { const int MOD = 1000000007; typedef unsigned long long ull; template class unordered_vmap; template using sptr = typename std::shared_ptr; template void fill(vector>& vec, const T& value) { for (vector& t : vec) { fill(t, value); } } template void fill(vector& vec, const T& value) { fill(vec.begin(), vec.end(), value); } template void resize(vector>& vec, int size1, int size2) { vec.resize(size1); for (vector& t : vec) { t.resize(size2); } } template class umap : public std::unordered_map { public: bool containsKey(const Key& key) const; bool containsValue(const Value& val) const; }; template bool umap::containsKey(const Key& key) const { return (this->find(key) != this->end()); } template bool umap::containsValue(const Value& val) const { for(auto itr = this->begin(); itr != this->end(); ++itr) { if (itr->second == val) { return true; } } return false; } class vmath { public: // 約数を全て求める O(√n) static ull calcDivisors(list* divisors, ull n) { divisors->clear(); if (n <= 0ull) { return 0ull; } divisors->push_back(1ull); if (n != 1ull) { divisors->push_back(n); } for (ull i = 2ull; i * i <= n; ++i) { if (n % i == 0ull) { divisors->push_back(i); divisors->push_back(n / i); } } return divisors->size(); } // 約数の個数を返す O(√n) static ull calcDivisorNum(ull n) { if (n <= 0ull) { return 0ull; } ull count = 1ull; // for 1 if (n != 1ull) { ++count; // for n } // for 2~n-1 for (ull i = 2ull; i * i <= n; ++i) { if (n % i == 0ull) { count += 2ull; } } return count; } // 素因数分解 O(√n) static int decompositPrime(list* primes, ull n) { primes->clear(); if (n == 0) { return 0ull; } if (n == 1) { primes->push_back(1); return 1ull; } // 割る数の初期値 ull a = 2ull; // √n ≧ a ( n ≧ a * a ) の間ループ処理 while (n >= a * a) { if (n % a == 0ull) { // a で割り切れたら、a は素因数 primes->push_back(a); // そして、割られる数を a で割る n /= a; } else { // a で割り切れなかったら、 a を 1 増加させる a++; } } primes->push_back(n); return primes->size(); } // 素因数の数を返す O(√n) static ull calcPrimeNum(ull n) { if (n <= 1) { return n; } ull count = 0ull; // 割る数の初期値 ull a = 2ull; // √n ≧ a ( n ≧ a * a ) の間ループ処理 while (n >= a * a) { if (n % a == 0ull) { // a で割り切れたら、a は素因数 ++count; // そして、割られる数を a で割る n /= a; } else { // a で割り切れなかったら、 a を 1 増加させる a++; } } ++count; // for n return count; } // 階乗 static ull fact(ull x) { if (x == 0ull) { return 1ull; } else { return x * fact(x - 1ull); } } // 順列 nPr static ull permutation(int n, int r) { assert(n >= r); //return fact(n) / fact(n - r); ull result = 1; for (ull i = n; i > n - r; --i) { result *= i; } return result; } // 組み合わせ nCr // 先にmakePascalTriangleでパスカルの三角形を作成しておく必要がある static ull combination(int n, int r) { assert(n >= r); assert(n <= mPascalTriangleDepth); return mPascalTriangle[n][r]; } // 重複組合せ nHr = n+r-1Cr // 使いどころ:n人にr個を配るとき、同じ人に何個配っても良い場合とか // 4人に5個の◯を配るときa=2,b=0,c=2,d=1のとき、◯◯||◯◯|◯みたいになる。 // これは◯と|を混ぜた組み合わせで、◯の数がn,棒の数はr-1だから全体でn+r-1 // (n-r)で割ったものが順列n+r-1Prで、それを更にrで割っているからnHr = n+r-1Cr static ull repeatedCombination(int n, int r) { return combination(n + r - 1, r); } // パスカルの三角形。組み合わせの計算に使用するのでこれを先に作成しておく必要がある。 static void makePascalTriangle(int depth) { resize(mPascalTriangle, depth + 1, depth + 1); for (int i = 0; i <= depth; ++i) { mPascalTriangle[i][0] = 1; for (int j = 1; j <= i; ++j) { mPascalTriangle[i][j] = mPascalTriangle[i - 1][j] + mPascalTriangle[i - 1][j - 1]; } } mPascalTriangleDepth = depth; } // xのN桁目の数値を得る static ull getNDigitNumber(ull x, ull n) { return (x / pow(10ull, n - 1ull)) % 10; } // xのN桁目の数値を得る static int getNDigitNumber(int x, int n) { assert(n <= 10); return (x / pow(10, n - 1)) % 10; } // xのN乗を求める(バイナリ法) O(logN) static ull pow(ull x, ull n) { assert(x >= 0ull); assert(n >= 0ull); if (x == 0ull) { if (n == 0ull) { return 1ull; } else { return 0ull; } } ull result = 1ull; ull z = x; while (n > 0ull) { if (n & 1ull) { result *= z; } z *= z; n >>= 1; } return result; } // xのN乗を求める(バイナリ法) O(logN) static int pow(int x, int n) { assert(x >= 0); assert(n >= 0); if (x == 0) { if (n == 0) { return 1; } else { return 0; } } int result = 1; int z = x; while (n > 0) { if (n & 1) { result *= z; } z *= z; n >>= 1; } return result; } private: static int mPascalTriangleDepth; static vector> mPascalTriangle; }; int vmath::mPascalTriangleDepth = 0; vector> vmath::mPascalTriangle; class vmath_mod { public: // 階乗 static ull fact(ull x) { ull result = 1ull; for (ull i = 1ull; i <= x; ++i) { result *= i; result %= MOD; } return result; } // 順列 nPr static ull permutation(int n, int r) { assert(n >= r); //return fact(n) / fact(n - r); ull result = 1; for (ull i = n; i > n - r; --i) { result *= i; result %= MOD; } return result; } // 組み合わせ nCr // 先にmakePascalTriangleでパスカルの三角形を作成しておく必要がある static ull combination(int n, int r) { assert(n >= r); assert(n <= mPascalTriangleDepth); return mPascalTriangle[n][r]; } // 重複組合せ nHr = n+r-1Cr // 使いどころ:n人にr個を配るとき、同じ人に何個配っても良い場合とか // 4人に5個の◯を配るときa=2,b=0,c=2,d=1のとき、◯◯||◯◯|◯みたいになる。 // これは◯と|を混ぜた組み合わせで、◯の数がn,棒の数はr-1だから全体でn+r-1 // (n-r)で割ったものが順列n+r-1Prで、それを更にrで割っているからnHr = n+r-1Cr static ull repeatedCombination(int n, int r) { return combination(n + r - 1, r); } // パスカルの三角形。組み合わせの計算に使用するのでこれを先に作成しておく必要がある。 static void makePascalTriangle(int depth) { resize(mPascalTriangle, depth + 1, depth + 1); for (int i = 0; i <= depth; ++i) { mPascalTriangle[i][0] = 1; for (int j = 1; j <= i; ++j) { mPascalTriangle[i][j] = (mPascalTriangle[i - 1][j] + mPascalTriangle[i - 1][j - 1]) % MOD; } } mPascalTriangleDepth = depth; } // xのN桁目の数値を得る static ull getNDigitNumber(ull x, ull n) { return (x / pow(10ull, n - 1ull)) % 10; } // xのN桁目の数値を得る static int getNDigitNumber(int x, int n) { assert(n <= 10); return (x / pow(10, n - 1)) % 10; } // xのN乗を求める O(n) static ull pow(ull x, ull n) { if (x == 0ull) { if (n == 0ull) { return 1ull; } else { return 0ull; } } ull result = 1ull; for (ull i = 0ull; i < n; ++i) { result *= x; result %= MOD; } return result; } // xのN乗を求める O(n) static int pow(int x, int n) { assert(x >= 0); assert(n >= 0); if (x == 0) { if (n == 0) { return 1; } else { return 0; } } int result = 1; for (int i = 0; i < n; ++i) { result *= x; result %= MOD; } return result; } private: static int mPascalTriangleDepth; static vector> mPascalTriangle; }; int vmath_mod::mPascalTriangleDepth = 0; vector> vmath_mod::mPascalTriangle; } using namespace ValLib; int main() { ull N; cin >> N; list primes; vmath::decompositPrime(&primes, N); /* 2個以上が0個なら、素因数の数が奇数ならAの勝ち、偶数ならBの勝ち 2個以上が1個以上あるなら、2個以上の素因数の種類が奇数ならAの勝ち、偶数ならBの勝ち */ unordered_map pCount; for (auto t : primes) { pCount[t]++; } if (all_of(pCount.begin(), pCount.end(), [](const pair& t) { return t.second <= 1; })) { if (pCount.size() % 2 == 0) { cout << "Bob" << endl; } else { cout << "Alice" << endl; } return 0; } int count = 0; for (auto p : pCount) { if (p.second >= 2) { ++count; } } if (count % 2 == 0) { cout << "Bob" << endl; } else { cout << "Alice" << endl; } getchar(); getchar(); }