結果

問題 No.2 素因数ゲーム
ユーザー wahr69wahr69
提出日時 2015-09-03 17:13:57
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 12,809 bytes
コンパイル時間 1,012 ms
コンパイル使用メモリ 101,216 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-26 02:35:49
合計ジャッジ時間 2,768 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 WA -
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 WA -
testcase_12 AC 2 ms
4,376 KB
testcase_13 WA -
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 WA -
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 2 ms
4,384 KB
testcase_29 AC 1 ms
4,380 KB
testcase_30 AC 2 ms
4,376 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]++;
	}

	if (all_of(pCount.begin(), pCount.end(), [](const pair<ull, ull>& 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();
}
0