結果

問題 No.2 素因数ゲーム
コンテスト
ユーザー @abcde
提出日時 2019-06-05 01:51:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 3,237 bytes
コンパイル時間 1,957 ms
コンパイル使用メモリ 181,824 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-26 13:55:31
合計ジャッジ時間 3,071 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

// 2 の 30乗 = 1073741824 > 100000000
int dp[30];

// Use of dynamic bitset to convert decimal numbers.
// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers
// 10進数 → 2進数.
// @param n: 2進数へ変換したい10進数.
// @param d: 2進数表記する桁数.
// @return: 2進数.
string decimalToBinary(LL n, int d) {

    // 1. ゼロの場合.
    string ret = "";
    if(n == 0){
        while(ret.size() < d) ret = "0" + ret;
        return ret;
    }
    
    // 2. ゼロでない場合.
    LL ln = abs(n);
    do{
        ret = string((ln & 1) ? "1" : "0") + ret;
    }while((ln /= 2) > 0);
    while(ret.size() < d) ret = "0" + ret;
    
    // 3. 負数の場合.
    if(n < 0) ret = "-" + ret;
    return ret;

}

// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return ret: 素因数分解 の 結果 を 返却.
map<LL, int> getAllDivisors(LL X) {
    
    // 1. X を 2で割り切れなくなるまで割っていく.
    map<LL, int> ret;
    while(X % 2 == 0) ret[2]++, X >>= 1;
    
    // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    for(LL i = 3; i <= sqrt(X); i += 2){
        while(X % i == 0){
            ret[i]++;
            X /= i;
        }
    }
    
    // 3. X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ret[X]++;
    
    // 4. 出力.
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    scanf("%llu", &N);

    // 2. 与えられた正の整数について, 素因数分解を行う.
    map<LL, int> divisors = getAllDivisors(N);
    // ex.
    // N = 1020304030201
    // 73 2
    // 101 2
    // 137 2
    // for(auto &p : divisors) cout << p.first << " " << p.second << endl;
    
    // 3. Alice, Bob の 勝者 を 検討..
    // ニム（複数山の石取りゲーム）の必勝法.
    // https://mathtrain.jp/nim
    // 3-1. 各素因数の出現回数を, 2進数へ変換して保存.
    vector<string> v;
    for(auto &p : divisors) v.push_back(decimalToBinary(p.second, 30));
    
    // 3-2. 前項で計算した2進数の各桁和を確認.
    for(auto &p : v){
        // cout << "p=" << p << endl;
        string b = p;
        for(int i = 0; i < 30; i++) dp[i] += b[i] - '0';
    }
    
    // 3-3. 奇数が存在するかチェック.
    bool alice = false;
    for(int i = 0; i < 30; i++) if(dp[i] % 2 != 0) alice = true;
    
    // 4. 出力.
    // ex.
    // N = 999999999
    // 3 4
    // 37 1
    // 333667 1
    // p=000000000000000000000000000100
    // p=000000000000000000000000000001
    // p=000000000000000000000000000001
    // -> Alice が 勝利すると予想.
    // 
    // N = 1000000000
    // 2 9
    // 5 9
    // p=000000000000000000000000001001
    // p=000000000000000000000000001001
    // -> Bob が 勝利すると予想.
    if(alice) printf("%s\n", "Alice");
    else      printf("%s\n", "Bob");
    return 0;
    
}
0