結果

問題 No.103 素因数ゲーム リターンズ
ユーザー codershifthcodershifth
提出日時 2015-10-02 01:31:49
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,847 bytes
コンパイル時間 1,664 ms
コンパイル使用メモリ 172,708 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-19 19:02:19
合計ジャッジ時間 2,405 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

template <typename T>
std::map<T,int> primeFactor(T n) {
        std::map<T,int> res;
        for (T i = 2; i*i <= n; ++i)
        {
            while (n%i==0)
            {
                ++res[i];
                n /= i;
            }
        }
        if (n!= 1)
            res[n] = 1;
        return res;
}
class PrimeGame {
public:
    void solve(void) {
            int N;
            cin>>N;
            auto primes = primeFactor(N);
            map<int,int> memo;

            // 各素因数を山の種類、素因数の冪数を山の高さとすると
            // Nim に帰着できる。
            function<int(int)> grundy = [&](int n) {
                if (memo.count(n))
                    return memo[n];
                if (n <= 1)
                    return (memo[n] = 0);
                set<int> S;
                for (auto pk : primes)
                {
                    int p,k;
                    tie(p,k) = pk;
                    int tmp(n);
                    while (tmp % p == 0)
                    {
                        tmp /= p;
                        S.insert(grundy(tmp));
                    }
                }
                int res = 0;
                while (S.count(res))
                    ++res;
                return (memo[n] = res);
            };
            if (grundy(N))
                cout<<"Alice"<<endl;
            else
                cout<<"Bob"<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new PrimeGame();
        obj->solve();
        delete obj;
        return 0;
}

#endif
0