結果

問題 No.2 素因数ゲーム
ユーザー 久我山菜々久我山菜々
提出日時 2018-09-29 15:51:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 938 bytes
コンパイル時間 1,179 ms
コンパイル使用メモリ 105,824 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-08 00:52:43
合計ジャッジ時間 1,984 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
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 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'std::pair<int, int> factor_imp(int)':
main.cpp:9:20: warning: narrowing conversion of 'std::sqrt<int>(n)' from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'int' [-Wnarrowing]
    9 |   int max{std::sqrt(n)};
      |           ~~~~~~~~~^~~

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>

// 割れた数, 商
std::pair<int, int> factor_imp(int n) {
  int max{std::sqrt(n)};
  for(int i{2}; i < max + 1; ++i) {
    if(n % i == 0) {
      return std::make_pair(i, n / i);
    }
  }
  return std::make_pair(n, 1);
}

// <素因数, 羃>
std::map<int, int> factor(int n) {
  std::map<int, int> map;
  do {
    auto v = factor_imp(n);
    ++map[v.first];
    n = v.second;
  } while(n != 1);
  return map;
}

// 奇数個の素数の積を渡されると勝ち。
// 偶数個なら負け。
// 1つだけn次、あとは全部1次のものを渡されると、勝ち。
// 全ての山の石の数のbitxorが0なら後手必勝 らしいよ。

int main(int, char**) {
  int N;
  std::cin >> N;

  auto map = factor(N);
  int f{};
  for(auto e: map) {
    f ^= e.second;
  }

  std::cout << (f ? "Alice" : "Bob") << std::endl;

  return 0;
}
0