結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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次のものを渡されると、勝ち。
// n次のものが偶数個だと負け、奇数なら勝ち？

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

  auto map = factor(N);
  int count1{};
  int count2p{};
  for(auto e: map) {
    if(e.second == 1) ++count1;
    if(e.second > 1) ++count2p;
    std::cout << e.first << ": " << e.second << std::endl;
  }

  if(count2p == 0) {
    std::cout << ((count1 % 2) ? "Alice" : "Bob") << std::endl;
  } else if(count2p % 2 == 0) {
    std::cout << "Bob" << std::endl;
  } else {
    std::cout << "Alice" << std::endl;
  }

  return 0;
}
0