結果

問題 No.2 素因数ゲーム
コンテスト
ユーザー 久我山菜々
提出日時 2018-09-29 15:51:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 938 bytes
コンパイル時間 917 ms
コンパイル使用メモリ 102,368 KB
最終ジャッジ日時 2025-01-06 14:10:50
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
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