結果

問題 No.2 素因数ゲーム
コンテスト
ユーザー 久我山菜々
提出日時 2018-09-29 15:47:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,211 bytes
コンパイル時間 1,070 ms
コンパイル使用メモリ 103,036 KB
最終ジャッジ日時 2025-01-06 14:10:42
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 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次のものを渡されると、勝ち。
// 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