#47139 (C++11) No.2 素因数ゲーム

提出ソース

結果

問題	No.2 素因数ゲーム
ユーザー	wahr69
提出日時	2015-09-03 17:13:57
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	12,809 bytes
コンパイル時間	1,112 ms
コンパイル使用メモリ	99,588 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-18 21:54:53
合計ジャッジ時間	2,032 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	WA	-
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,944 KB
testcase_11	WA	-
testcase_12	AC	1 ms 6,940 KB
testcase_13	WA	-
testcase_14	AC	1 ms 6,940 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	1 ms 6,940 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,940 KB
testcase_21	AC	1 ms 6,944 KB
testcase_22	WA	-
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	1 ms 6,944 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	1 ms 6,940 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	1 ms 6,940 KB
testcase_29	AC	1 ms 6,940 KB
testcase_30	AC	1 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード