結果
| 問題 |
No.103 素因数ゲーム リターンズ
|
| コンテスト | |
| ユーザー |
 chabudaisanta
|
| 提出日時 | 2025-10-16 19:52:47 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 21,071 bytes |
| コンパイル時間 | 5,242 ms |
| コンパイル使用メモリ | 306,960 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-10-16 19:52:53 |
| 合計ジャッジ時間 | 6,361 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 20 |
ソースコード
#line 2 "/home/chabudaisanta/lib/gwen/src/gwen/my_template.hpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <compare>
#include <concepts>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <locale>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#line 2 "/home/chabudaisanta/lib/gwen/src/gwen/dump.hpp"
#line 17 "/home/chabudaisanta/lib/gwen/src/gwen/dump.hpp"
#line 2 "/home/chabudaisanta/lib/gwen/src/gwen/types.hpp"
#include <cstdint>
namespace gwen {
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
} // namespace gwen
#line 19 "/home/chabudaisanta/lib/gwen/src/gwen/dump.hpp"
namespace gwen {
//-------------------------
// standard types
//-------------------------
constexpr inline std::string to_str() { return ""; }
constexpr inline std::string to_str(bool b) { return b ? "true" : "false"; }
constexpr inline std::string to_str(char c) { return std::string{c}; }
constexpr inline std::string to_str(const char* cs) { return std::string{cs}; }
constexpr inline std::string to_str(const std::string& str) { return str; }
constexpr inline std::string to_str(std::nullptr_t) { return "nullptr"; }
constexpr inline std::string to_str(u128 x) {
if (x == 0) return "0";
std::string ret;
while (x) {
ret.push_back(static_cast<char>('0' + (x % 10)));
x /= 10;
}
std::reverse(ret.begin(), ret.end());
return ret;
}
constexpr inline std::string to_str(i128 x) {
if (x < 0) return std::string{'-'} + to_str(static_cast<u128>(-x));
return to_str(static_cast<u128>(x));
}
template <std::integral T> std::string to_str(T x) { return std::to_string(x); }
template <std::floating_point T> std::string to_str(T f) {
return std::to_string(f);
}
//-------------------------
// prototype
//-------------------------
// pair / tuple
template <typename T1, typename T2>
std::string to_str(const std::pair<T1, T2>& p);
template <typename... Ts> std::string to_str(const std::tuple<Ts...>& t);
// input iterator helper
template <std::input_iterator Iterator>
std::string to_str(Iterator begin,
Iterator end,
const std::string& partition = ", ",
char pb = '\0',
char pe = '\0');
// sequence containers
template <typename T> std::string to_str(const std::vector<T>& sc);
template <typename T, std::size_t N>
std::string to_str(const std::array<T, N>& sc);
template <typename T> std::string to_str(const std::deque<T>& sc);
template <typename T, std::size_t N> std::string to_str(const T (&sc)[N]);
// set containers
template <typename T> std::string to_str(const std::set<T>& se);
template <typename T> std::string to_str(const std::multiset<T>& se);
template <typename T> std::string to_str(const std::unordered_set<T>& se);
template <typename T> std::string to_str(const std::unordered_multiset<T>& se);
// map containers
template <typename K, typename V> std::string to_str(const std::map<K, V>& mp);
template <typename K, typename V>
std::string to_str(const std::multimap<K, V>& mp);
template <typename K, typename V>
std::string to_str(const std::unordered_map<K, V>& mp);
template <typename K, typename V>
std::string to_str(const std::unordered_multimap<K, V>& mp);
template <std::input_iterator Iterator>
std::string to_str_map_helper(Iterator begin, Iterator end);
// user-defined
template <typename T>
requires requires(const T& t) { gwen::to_str(t.val()); }
std::string to_str(const T& t);
template <typename T>
requires requires(const T& t) { gwen::to_str(t.dump()); }
std::string to_str(const T& t);
//-------------------------
// implementation
//-------------------------
// pair / tuple
template <typename T1, typename T2>
std::string to_str(const std::pair<T1, T2>& p) {
return std::string{'('} + to_str(p.first) + ", " + to_str(p.second) + ')';
}
template <typename... Ts> std::string to_str(const std::tuple<Ts...>& t) {
std::string ret{'('};
bool first = true;
std::apply(
[&](const auto&... args) {
((ret += (first ? "" : ", "), ret += gwen::to_str(args),
first = false),
...);
},
t);
return ret + ')';
}
template <typename... Args>
inline std::string to_str_variadic(const Args&... args) {
std::string ret;
std::size_t index = 0;
auto process_one = [&](const auto& arg) {
if (index++ > 0) {
ret += ", ";
}
if constexpr (requires { gwen::to_str(arg); }) {
ret += gwen::to_str(arg);
}
else {
ret += "[?]";
}
};
(process_one(args), ...);
return ret;
}
// input iterator helper
template <std::input_iterator Iterator>
std::string to_str(Iterator begin,
Iterator end,
const std::string& partition,
char pb,
char pe) {
std::string ret;
if (pb) ret += pb;
for (auto it = begin; it != end; ++it) {
if (it != begin) ret += partition;
ret += to_str(*it);
}
if (pe) ret += pe;
return ret;
}
// sequence containers
template <typename T> std::string to_str(const std::vector<T>& sc) {
return to_str(sc.begin(), sc.end(), ", ", '[', ']');
}
template <typename T, std::size_t N>
std::string to_str(const std::array<T, N>& sc) {
return to_str(sc.begin(), sc.end(), ", ", '[', ']');
}
template <typename T> std::string to_str(const std::deque<T>& sc) {
return to_str(sc.begin(), sc.end(), ", ", '[', ']');
}
template <typename T, std::size_t N> std::string to_str(const T (&sc)[N]) {
return to_str(sc.begin(), sc.end(), ", ", '[', ']');
}
// set containers
template <typename T> std::string to_str(const std::set<T>& se) {
return to_str(se.begin(), se.end(), ", ", '{', '}');
}
template <typename T> std::string to_str(const std::multiset<T>& se) {
return to_str(se.begin(), se.end(), ", ", '{', '}');
}
template <typename T> std::string to_str(const std::unordered_set<T>& se) {
return to_str(se.begin(), se.end(), ", ", '{', '}');
}
template <typename T> std::string to_str(const std::unordered_multiset<T>& se) {
return to_str(se.begin(), se.end(), ", ", '{', '}');
}
// map containers
template <typename K, typename V> std::string to_str(const std::map<K, V>& mp) {
return to_str_map_helper(mp.begin(), mp.end());
}
template <typename K, typename V>
std::string to_str(const std::multimap<K, V>& mp) {
return to_str_map_helper(mp.begin(), mp.end());
}
template <typename K, typename V>
std::string to_str(const std::unordered_map<K, V>& mp) {
return to_str_map_helper(mp.begin(), mp.end());
}
template <typename K, typename V>
std::string to_str(const std::unordered_multimap<K, V>& mp) {
return to_str_map_helper(mp.begin(), mp.end());
}
template <std::input_iterator Iterator>
std::string to_str_map_helper(Iterator begin, Iterator end) {
std::string ret{'{'};
for (auto it = begin; it != end; ++it) {
if (it != begin) ret += ", ";
ret += '(' + to_str(it->first) + ": " + to_str(it->second) + ')';
}
ret += '}';
return ret;
}
// user-defined
template <typename T>
requires requires(const T& t) { gwen::to_str(t.val()); }
std::string to_str(const T& t) {
return gwen::to_str(t.val());
}
template <typename T>
requires requires(const T& t) { gwen::to_str(t.dump()); }
std::string to_str(const T& t) {
return gwen::to_str(t.dump());
}
} // namespace gwen
#ifdef LOCAL
#define DEBUG(...) \
std::cerr << #__VA_ARGS__ << ": " << gwen::to_str_variadic(__VA_ARGS__) \
<< '\n'
#define DUMP(...) \
std::cerr << #__VA_ARGS__ << ": " << gwen::to_str_variadic(__VA_ARGS__) \
<< '\n'
#else
#define DEBUG(...) void(0)
#define DUMP(...) void(0)
#endif
// std::string += std::string は、atcoder環境なら線形時間でやってくれそう
// https://atcoder.jp/contests/abc379/submissions/69207872
#line 37 "/home/chabudaisanta/lib/gwen/src/gwen/my_template.hpp"
using gwen::i128;
using gwen::i32;
using gwen::i64;
using gwen::u128;
using gwen::u32;
using gwen::u64;
using ll = long long;
using ull = unsigned long long;
#define rep(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rp(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#ifdef LOCAL
#define BAR std::cerr << "----------------------------------------------\n"
#define S_BAR std::cerr << "------------------\n"
#else
#define BAR void(0)
#define S_BAR void(0)
#endif
constexpr std::pair<int, int> mv[] = {{0, 1}, {1, 0}, {0, -1},
{-1, 0}, {1, 1}, {1, -1},
{-1, -1}, {-1, 1}, {0, 0}};
constexpr int dw[] = {0, 0, -1, 1, -1, -1, 1, 1, 0};
constexpr int dh[] = {-1, 1, 0, 0, -1, 1, -1, 1, 0};
constexpr int mod998 = 998244353, mod107 = 1000000007, mod109 = 1000000009,
mod31 = 2147483647;
constexpr ll mod61 = (1LL << 61) - 1;
constexpr int iINF = (1 << 30) + 1;
constexpr ll liINF = (1LL << 60) + 1;
constexpr char EL = '\n', SPA = ' ';
std::pair<int, int> mv_to(int hi, int wi, int dir) {
assert(0 <= dir && dir < 9);
return std::make_pair(hi + dh[dir], wi + dw[dir]);
}
template <typename T1, typename T2> inline bool chmax(T1& a, T2 b) {
return (a < b ? a = b, true : false);
}
template <typename T1, typename T2> inline bool chmin(T1& a, T2 b) {
return (a > b ? a = b, true : false);
}
template <std::integral T> inline bool isIn(T x, T l, T r) {
return (l <= x) && (x < r);
}
template <std::integral T> inline bool isOut(T x, T l, T r) {
return (x < l) || (r <= x);
}
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
for (auto it = vec.begin(); it != vec.end(); it++)
os << *it << (it == prev(vec.end()) ? "" : " ");
return os;
}
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
for (T& e : vec) is >> e;
return is;
}
void yon(bool b) { std::cout << (b ? "Yes\n" : "No\n"); }
template <typename T>
std::vector<int> idxsort(const std::vector<T>& vec, bool rev = false) {
std::vector<int> ret(vec.size());
std::iota(ret.begin(), ret.end(), 0);
sort(ret.begin(), ret.end(), [&vec, &rev](int a, int b) {
return (rev ? vec[a] > vec[b] : vec[a] < vec[b]);
});
return ret;
}
template <std::integral T> T ceil_div(T x, T y) {
assert(y != 0);
T d = x / y;
return d * y == x ? d : d + ((x > 0) ^ (y < 0));
}
template <std::integral T> T floor_div(T x, T y) {
assert(y != 0);
T d = x / y;
return d * y == x ? d : d - ((x < 0) ^ (y < 0));
}
template <std::integral T> T out_div(T x, T y) {
assert(y != 0);
T d = x / y;
return d * y == x ? d : ((x > 0) == (y > 0)) ? d + 1 : d - 1;
}
// https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3605r0.pdf
template <std::unsigned_integral T> constexpr T isqrt(const T n) noexcept {
if (n <= T{1}) return n;
T i_current{0}, i_next{T(T{1} << ((std::bit_width(T(n - 1)) + 1) >> 1))};
do {
i_current = i_next;
i_next = T((i_current + n / i_current) >> 1);
} while (i_next < i_current);
return i_current;
}
template <typename T> constexpr T sq(T x) { return x * x; }
template <std::integral T> constexpr T choose2(T x) { return x * (x - 1) / 2; }
template <std::integral T1, std::integral T2>
constexpr T1 getBit(T1 bit, T2 i) {
return bit & (static_cast<T1>(1) << i);
}
template <std::integral T1, std::integral T2>
constexpr T1 setBit(T1 bit, T2 i) {
return bit | (static_cast<T1>(1) << i);
}
template <std::integral T1, std::integral T2>
constexpr T1 clearBit(T1 bit, T2 i) {
return bit & ~(static_cast<T1>(1) << i);
}
template <std::integral T1, std::integral T2>
constexpr T1 toggleBit(T1 bit, T2 i) {
return bit ^ (static_cast<T1>(1) << i);
}
template <typename Iterator> auto runlength(Iterator begin, Iterator end) {
using ValueType = typename std::iterator_traits<Iterator>::value_type;
using CountType = int;
std::vector<std::pair<ValueType, CountType>> ret;
for (auto it = begin; it != end; ++it) {
if (ret.empty() || ret.back().first != *it) ret.emplace_back(*it, 0);
ret.back().second++;
}
return ret;
}
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using mint998 = atcoder::modint998244353;
using mint107 = atcoder::modint1000000007;
#endif
#if __has_include(<gmpxx.h>)
#include <gmpxx.h>
using gmp_int = mpz_class;
#endif
/*
#if __has_include(<Eigen/Dense>)
#include <Eigen/Dense>
#endif
*/
#line 2 "/home/chabudaisanta/lib/gwen/src/gwen/math/prime.hpp"
#line 4 "/home/chabudaisanta/lib/gwen/src/gwen/math/prime.hpp"
#line 2 "/home/chabudaisanta/lib/gwen/src/gwen/mod/modint.hpp"
// https://rsk0315.hatenablog.com/entry/2022/11/27/060616
#line 4 "/home/chabudaisanta/lib/gwen/src/gwen/mod/modint.hpp"
#line 2 "/home/chabudaisanta/lib/gwen/src/gwen/mod/mod.hpp"
#line 4 "/home/chabudaisanta/lib/gwen/src/gwen/mod/mod.hpp"
#line 6 "/home/chabudaisanta/lib/gwen/src/gwen/mod/mod.hpp"
namespace gwen {
i64 pow_mod(i64 x, i64 n, i64 m = 998244353) {
if (x == 0) return (n ? 0 : 1);
x %= m;
i64 ret = 1;
while (n) {
if (n & 1) ret = (ret * x) % m;
x = (x * x) % m;
n >>= 1;
}
return ret;
}
i64 inv_mod(i64 a, i64 m = 998244353) {
i64 b = m, u = 1, v = 0;
while (b) {
i64 t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
u64 inv_mod_64(u64 a, u64 m) {
i128 s = m, t = a;
i128 x = 0, y = 1;
while (t) {
i128 u = s / t;
s -= t * u;
x -= y * u;
std::swap(s, t);
std::swap(x, y);
}
// assert(s == 1); // gcd(a,m)が1でなければ逆元は存在しない
return (x % m + m) % m;
}
} // namespace gwen
#line 7 "/home/chabudaisanta/lib/gwen/src/gwen/mod/modint.hpp"
namespace gwen {
class dynamic_modint64 {
using m64 = dynamic_modint64;
static inline u64 n = 1;
static inline u64 ns = 0;
static inline u64 r2 = 0;
static inline constexpr u64 msk = -1;
u64 reduce_mul(u64 a, u64 b) const {
u128 t = static_cast<u128>(a) * b;
u128 m = (t * ns) & msk; // maybe unnecessary mask ?
a = (m * n + t) >> 64; // t ← (t + mN) / R
return a < n ? a : a - n;
}
u64 tr;
public:
static void set_mod(u64 n_) {
assert(n_ < (1ull << 62));
assert(n_ & 1);
n = n_;
ns = n;
for (int i = 0; i < 5; ++i) ns *= 2 - ns * n;
assert(ns * n == 1);
ns = -ns;
r2 = -static_cast<u128>(n) % n;
}
dynamic_modint64() : tr(0) {}
// need 0 <= abs(x) < RN
template <std::unsigned_integral T>
dynamic_modint64(T x) : tr(reduce_mul(x, r2)) {}
template <std::signed_integral T> dynamic_modint64(T x) : tr(0) {
if (x < 0)
sub(m64{static_cast<u64>(-x)});
else
tr = reduce_mul(x, r2);
}
u64 val() const { return reduce_mul(tr, 1); }
// basic operation
m64& sub(const m64& x) {
if (tr < x.tr) tr += n;
tr -= x.tr;
return *this;
}
m64& add(const m64& x) {
tr += x.tr;
if (tr >= n) tr -= n;
return *this;
}
m64& mul(const m64& x) {
tr = reduce_mul(tr, x.tr);
return *this;
}
// operator overload
m64& operator+=(const m64& x) { return add(x); }
m64 operator+(const m64& x) const {
m64 tmp = *this;
tmp.add(x);
return tmp;
}
m64& operator-=(const m64& x) { return sub(x); }
m64 operator-(const m64& x) const {
m64 tmp = *this;
tmp.sub(x);
return tmp;
}
m64& operator*=(const m64& x) { return mul(x); }
m64 operator*(const m64& x) const {
m64 tmp = *this;
tmp.mul(x);
return tmp;
}
// operator overload (integral)
template <std::integral T> m64& operator+=(T x) { return add(m64(x)); }
template <std::integral T> m64 operator+(T x) const {
return *this + m64(x);
}
template <std::integral T> m64& operator-=(T x) { return sub(m64(x)); }
template <std::integral T> m64 operator-(T x) const {
return *this - m64(x);
}
template <std::integral T> m64& operator*=(T x) { return mul(m64(x)); }
template <std::integral T> m64 operator*(T x) const {
return *this * m64(x);
}
template <std::integral T> m64 pow(T x) const {
assert(x >= 0);
m64 ret(1);
m64 tmp(*this);
while (x) {
if (x & 1) ret.mul(tmp);
tmp.tr = reduce_mul(tmp.tr, tmp.tr);
x >>= 1;
}
return ret;
}
};
} // namespace gwen
#line 7 "/home/chabudaisanta/lib/gwen/src/gwen/math/prime.hpp"
namespace gwen {
namespace internal {
struct prime_factorize_table {
i32 n;
std::vector<i32> p; // p[i] = 0: i is prime (or 1/0)
prime_factorize_table() : n(2), p(2, 0) {}
void extend() {
assert(n < (1 << 30));
n <<= 1;
p.resize(n, 0);
for (int i = 2; i < n; ++i)
if (!p[i]) {
for (i64 j = i64(i) * i; j < n; j += i) {
p[j] = i;
}
}
}
// if x <= max() can factorize
// else cannot factorize
i32 max() const { return n - 1; }
};
} // namespace internal
std::vector<i32> factorize(i32 x) {
assert(0 < x && x < (1 << 30));
static gwen::internal::prime_factorize_table table;
while (table.max() < x) table.extend();
std::vector<i32> ret;
while (table.p[x] != 0) {
// if p[x] = 0, x is prime
ret.emplace_back(table.p[x]);
x /= table.p[x];
}
if (x != 1) ret.emplace_back(x);
return ret;
}
bool miller32(u32 n) {
assert(n < 4759123141u);
static u64 a[3] = {2, 7, 61};
using mint = dynamic_modint64;
mint::set_mod(n);
u64 s = 0, d = n - 1;
while (!(d & 1)) {
++s;
d >>= 1;
}
for (int i = 0; i < 3; ++i) {
if (n <= a[i]) return true;
mint x{a[i]};
x = x.pow(d);
if (x.val() != 1u) {
u64 t;
for (t = 0; t < s; ++t) {
if (x.val() == n - 1) break;
x *= x;
}
if (t == s) return false;
}
}
return true;
}
bool miller64(u64 n) {
static u64 a[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
using mint = dynamic_modint64;
mint::set_mod(n);
u64 s = 0, d = n - 1;
while (!(d & 1)) {
++s;
d >>= 1;
}
for (int i = 0; i < 7; ++i) {
if (n <= a[i]) return true;
mint x{a[i]};
x = x.pow(d);
u64 t;
if (x.val() != 1u) {
for (t = 0; t < s; ++t) {
if (x.val() == n - 1) break;
x *= x;
}
if (t == s) return false;
}
}
return true;
}
bool is_prime_small(i32 n) {
static gwen::internal::prime_factorize_table table;
while (table.max() < n) table.extend();
return !table.p[n];
}
bool miller(u64 n) {
if (n <= 1)
return false;
else if (n == 2)
return true;
else if (!(n & 1))
return false;
else if (n < (1u << 23))
return is_prime_small(n);
else if (n < 4759123141u)
return miller32(n);
else
return miller64(n);
}
} // namespace gwen
#line 3 "a.cpp"
using namespace std;
void solve() {
i32 N; cin >> N;
vector<i32> M(N); cin >> M;
vector<vector<i32>> F(N);
u32 grundy = 0;
rp(i,N) {
F[i] = gwen::factorize(M[i]);
DUMP(F[i]);
map<i32,u32> cnt;
for(i32 f : F[i]) cnt[f]++;
u32 g = 0;
for(auto [k, v] : cnt) {
g ^= v % 3;
}
grundy ^= g;
DUMP(g);
}
cout << (grundy ? "Alice" : "Bob") << EL;
}
int main(void) {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cout << std::fixed << std::setprecision(16);
int t = 1;
// cin >> t;
while (t--) solve();
std::cerr << "execution time: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000
<< "(ms)" << EL;
return 0;
}