C++ Library for Competitive Programming
/*
* @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;
}