ゲーム/ニム
(test/game/nim.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://yukicoder.me/problems/no/2

Depends on

• ニム (nim) (include/emthrm/game/nim.hpp)
• 素因数分解 (prime factorization) (include/emthrm/math/prime_factorization.hpp)

Code

/*
 * @title ゲーム/ニム
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/2
 */

#include <iostream>
#include <ranges>
#include <utility>
#include <vector>

#include "emthrm/game/nim.hpp"
#include "emthrm/math/prime_factorization.hpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a;
  // GCC 12 adopted P2415.
  const std::vector<std::pair<int, int>> pf = emthrm::prime_factorization(n);
  const auto ev = pf | std::views::values;
  // const auto ev = emthrm::prime_factorization(n) | std::views::values;
  std::cout << (emthrm::nim(std::vector<int>(ev.begin(), ev.end())) ?
                "Alice\n" : "Bob\n");
  return 0;
}

#line 1 "test/game/nim.test.cpp"
/*
 * @title ゲーム/ニム
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/2
 */

#include <iostream>
#include <ranges>
#include <utility>
#include <vector>

#line 1 "include/emthrm/game/nim.hpp"



#line 5 "include/emthrm/game/nim.hpp"

namespace emthrm {

template <typename T>
bool nim(const std::vector<T>& a) {
  long long x = 0;
  for (const T e : a) x ^= e;
  return x != 0;
}

}  // namespace emthrm


#line 1 "include/emthrm/math/prime_factorization.hpp"



#line 6 "include/emthrm/math/prime_factorization.hpp"

namespace emthrm {

template <typename T>
std::vector<std::pair<T, int>> prime_factorization(T n) {
  std::vector<std::pair<T, int>> res;
  for (T i = 2; i * i <= n; ++i) {
    if (n % i == 0) [[unlikely]] {
      int exponent = 0;
      for (; n % i == 0; n /= i) {
        ++exponent;
      }
      res.emplace_back(i, exponent);
    }
  }
  if (n > 1) res.emplace_back(n, 1);
  return res;
}

}  // namespace emthrm


#line 14 "test/game/nim.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a;
  // GCC 12 adopted P2415.
  const std::vector<std::pair<int, int>> pf = emthrm::prime_factorization(n);
  const auto ev = pf | std::views::values;
  // const auto ev = emthrm::prime_factorization(n) | std::views::values;
  std::cout << (emthrm::nim(std::vector<int>(ev.begin(), ev.end())) ?
                "Alice\n" : "Bob\n");
  return 0;
}

Back to top page