結果
| 問題 | No.2 素因数ゲーム |
| コンテスト | |
| ユーザー |
 wahr69
|
| 提出日時 | 2015-09-04 13:07:05 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 12,558 bytes |
| コンパイル時間 | 1,283 ms |
| コンパイル使用メモリ | 98,188 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-26 11:50:19 |
| 合計ジャッジ時間 | 2,107 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 31 |
ソースコード
#include <iostream>
#include <array>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <sstream>
#include <memory>
#include <cassert>
#include <functional>
#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 <typename Key, typename Value>
class unordered_vmap;
template <typename T>
using sptr = typename std::shared_ptr<T>;
template<typename T>
void fill(vector<vector<T>>& vec, const T& value) {
for (vector<T>& t : vec) {
fill(t, value);
}
}
template<typename T>
void fill(vector<T>& vec, const T& value) {
fill(vec.begin(), vec.end(), value);
}
template<typename T>
void resize(vector<vector<T>>& vec, int size1, int size2) {
vec.resize(size1);
for (vector<T>& t : vec) {
t.resize(size2);
}
}
template<typename Key, typename Value>
class umap : public std::unordered_map<Key, Value> {
public:
bool containsKey(const Key& key) const;
bool containsValue(const Value& val) const;
};
template<typename Key, typename Value>
bool umap<Key, Value>::containsKey(const Key& key) const {
return (this->find(key) != this->end());
}
template<typename Key, typename Value>
bool umap<Key, Value>::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<ull>* 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<ull>* 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<vector<ull>> mPascalTriangle;
};
int vmath::mPascalTriangleDepth = 0;
vector<vector<ull>> 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<vector<ull>> mPascalTriangle;
};
int vmath_mod::mPascalTriangleDepth = 0;
vector<vector<ull>> vmath_mod::mPascalTriangle;
}
using namespace ValLib;
int main()
{
ull N;
cin >> N;
list<ull> primes;
vmath::decompositPrime(&primes, N);
/*
２個以上が０個なら、素因数の数が奇数ならAの勝ち、偶数ならBの勝ち
２個以上が１個以上あるなら、２個以上の素因数の種類が奇数ならAの勝ち、偶数ならBの勝ち
*/
unordered_map<ull, ull> pCount;
for (auto t : primes) {
pCount[t]++;
}
int x = 0;
for (auto p : pCount) {
x ^= p.second;
}
if (x == 0) {
cout << "Bob" << endl;
} else {
cout << "Alice" << endl;
}
getchar();
getchar();
}