結果

問題 No.2 素因数ゲーム
ユーザー wahr69wahr69
提出日時 2015-09-04 13:07:05
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 12,558 bytes
コンパイル時間 891 ms
コンパイル使用メモリ 98,660 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-08 00:11:35
合計ジャッジ時間 1,737 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 1 ms
6,944 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 1 ms
6,944 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 1 ms
6,944 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 1 ms
6,940 KB
testcase_29 AC 1 ms
6,940 KB
testcase_30 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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();
}
0