#826238 (C++17) No.2 素因数ゲーム

• 問題: No.2 素因数ゲーム
• ユーザー: atree
• 提出日時: 2022-12-16 23:50:31
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 5,000 ms
• コード長: 10,630 bytes
• コンパイル時間: 2,232 ms
• コンパイル使用メモリ: 202,328 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-11-16 05:57:24
• 合計ジャッジ時間: 3,246 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,816 KB
testcase_03	AC	2 ms; 6,820 KB
testcase_04	AC	2 ms; 6,816 KB
testcase_05	AC	2 ms; 6,816 KB
testcase_06	AC	2 ms; 6,816 KB
testcase_07	AC	2 ms; 6,816 KB
testcase_08	AC	2 ms; 6,816 KB
testcase_09	AC	2 ms; 6,820 KB
testcase_10	AC	2 ms; 6,820 KB
testcase_11	AC	2 ms; 6,820 KB
testcase_12	AC	2 ms; 6,816 KB
testcase_13	AC	2 ms; 6,816 KB
testcase_14	AC	2 ms; 6,820 KB
testcase_15	AC	2 ms; 6,820 KB
testcase_16	AC	2 ms; 6,816 KB
testcase_17	AC	2 ms; 6,820 KB
testcase_18	AC	2 ms; 6,816 KB
testcase_19	AC	2 ms; 6,816 KB
testcase_20	AC	2 ms; 6,820 KB
testcase_21	AC	2 ms; 6,820 KB
testcase_22	AC	2 ms; 6,820 KB
testcase_23	AC	2 ms; 6,820 KB
testcase_24	AC	2 ms; 6,816 KB
testcase_25	AC	2 ms; 6,816 KB
testcase_26	AC	2 ms; 6,816 KB
testcase_27	AC	2 ms; 6,816 KB
testcase_28	AC	2 ms; 6,816 KB
testcase_29	AC	2 ms; 6,816 KB
testcase_30	AC	2 ms; 6,820 KB

ソースコード

// template {{{
#include <bits/stdc++.h>
#if __has_include(<debug.hpp>)
#    include <debug.hpp>
#else
#    define dbg(...) static_cast<void>(0)
#endif

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using usize = std::size_t;
using bit_t = u64;

constexpr auto operator""_i32(unsigned long long n) noexcept {
    return static_cast<std::int32_t>(n);
}
constexpr auto operator""_i64(unsigned long long n) noexcept {
    return static_cast<std::int64_t>(n);
}
constexpr auto operator""_u32(unsigned long long n) noexcept {
    return static_cast<std::uint32_t>(n);
}
constexpr auto operator""_u64(unsigned long long n) noexcept {
    return static_cast<std::uint64_t>(n);
}
constexpr auto operator""_uz(unsigned long long n) noexcept {
    return static_cast<size_t>(n);
}
constexpr auto operator""_bit(unsigned long long n) noexcept {
    return static_cast<bit_t>(n);
}

template<class T, T N = 2> inline constexpr auto INF = std::numeric_limits<T>::max() / N;

template<class T> constexpr inline std::enable_if_t<std::is_arithmetic_v<T>, T> power(T a, u32 b) {
    T ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans *= a;
        a *= a;
    }
    return ans;
}

template<class T> constexpr inline auto TEN(u32 n) {
    return power(static_cast<T>(10), n);
}

constexpr inline auto countr_zero(bit_t n) -> int {
    return n == 0 ? 64 : __builtin_ctzll(n);
}
constexpr inline auto countl_zero(bit_t n) -> int {
    return n == 0 ? 64 : __builtin_clzll(n);
}
constexpr inline auto countr_one(bit_t n) -> int {
    return n == std::numeric_limits<bit_t>::max() ? 64 : countr_zero(compl n);
}
constexpr inline auto countl_one(bit_t n) -> int {
    return n == std::numeric_limits<bit_t>::max() ? 64 : countl_zero(compl n);
}
constexpr inline auto mask(u32 n) -> bit_t {
    return (static_cast<bit_t>(1) << n) - 1;
}
constexpr inline auto popcount(bit_t n) -> int {
    return __builtin_popcountll(n);
}
constexpr inline auto is_pow2(bit_t n) -> bool {
    return (n & (n - 1)) == 0;
}
constexpr inline auto msb(bit_t n) -> int {
    return 63 - countl_zero(n);
}
constexpr inline auto bit_ceil(bit_t n) -> bit_t {
    return is_pow2(n) ? n : static_cast<bit_t>(1) << msb(n);
}
constexpr inline auto bit_floor(bit_t n) -> bit_t {
    return is_pow2(n) ? n : static_cast<bit_t>(1) << (msb(n) + 1);
}

template<class T, class U = T> constexpr auto chmin(T& a, U&& b) -> bool {
    return b < a ? a = std::forward<U>(b), true : false;
}
template<class T, class U = T> constexpr auto chmax(T& a, U&& b) -> bool {
    return a < b ? a = std::forward<U>(b), true : false;
}

template<class> struct is_tuple_like: std::false_type {};
template<class... Ts> struct is_tuple_like<std::tuple<Ts...>>: std::true_type {};
template<class T1, class T2> struct is_tuple_like<std::pair<T1, T2>>: std::true_type {};
template<class T, std::size_t N> struct is_tuple_like<std::array<T, N>>: std::true_type {};

template<class, class = std::void_t<>> struct is_printable: std::false_type {};
template<class T> struct is_printable<T, std::void_t<decltype(std::cout << std::declval<T>())>>: std::true_type {};

template<class, class = std::void_t<>> struct is_iteratable: std::false_type {};
template<class T>
struct is_iteratable<T, std::void_t<decltype(std::begin(std::declval<T>()), std::end(std::declval<T>()))>>:
    std::true_type {};

template<class, class = std::void_t<>> struct has_val: std::false_type {};
template<class T> struct has_val<T, std::void_t<decltype(std::declval<T>().val())>>: std::true_type {};

template<class T> struct is_1indexed: std::false_type {};
#define INDEXED_IMPL(type)                    \
    struct type##_##1 { using base = type; }; \
    template<> struct is_1indexed<type##_##1>: std::true_type {};
INDEXED_IMPL(int)
INDEXED_IMPL(size_t)
INDEXED_IMPL(i32)
INDEXED_IMPL(u32)
INDEXED_IMPL(i64)
INDEXED_IMPL(u64)
INDEXED_IMPL(usize)
#undef INDEXED_IMPL

template<class F> struct rec_lambda {
    F f;
    explicit constexpr rec_lambda(F&& f): f(std::forward<F>(f)) {}
    template<class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
        return f(*this, std::forward<Args>(args)...);
    }
};

template<class... Args> auto zip(const std::vector<Args>&... args) {
    std::size_t n = std::min({ std::size(args)... });
    std::vector<std::tuple<std::decay_t<Args>...>> ret(n);
    for (std::size_t i = 0; i < n; ++i) ret[i] = { args[i]... };
    return ret;
}

template<class T, size_t N> auto construct_vector(std::vector<size_t>& sizes, T x = std::decay_t<T>{}) {
    if constexpr (N == 1) {
        return std::vector<std::decay_t<T>>(sizes[0], x);
    } else {
        size_t size = sizes[N - 1];
        sizes.pop_back();
        return std::vector(size, construct_vector<T, N - 1>(sizes, x));
    }
}

template<class T, size_t N> decltype(auto) make_vector(size_t (&&sizes)[N], T&& x = std::decay_t<T>{}) {
    std::vector<size_t> s(N);
    for (size_t i = 0; i < N; ++i) s[i] = sizes[N - i - 1];
    if constexpr (std::is_invocable_v<std::decay_t<T>>) {
        auto ret = construct_vector<std::invoke_result_t<std::decay_t<T>>, N>(s);
        rec_lambda([](auto&& self, auto& v, auto&& f) {
            for (auto it = std::begin(v); it != std::end(v); ++it) {
                if constexpr (std::is_same_v<std::decay_t<decltype(*it)>, std::invoke_result_t<decltype(f)>>) *it = f();
                else self(*it, f);
            }
        })(ret, x);
        return ret;
    } else {
        return construct_vector<std::decay_t<T>, N>(s, x);
    }
}

template<class V> auto make_graph(size_t n, const std::vector<std::tuple<V, V>>& edges, bool is_directed = false) {
    std::vector graph(n, std::vector<size_t>{});
    for (const auto& [u, v]: edges) {
        graph[u].emplace_back(v);
        if (not is_directed) graph[v].emplace_back(u);
    }
    return graph;
}

template<class V, class W>
auto make_graph(size_t n, const std::vector<std::tuple<V, V, W>>& edges, bool is_directed = false) {
    std::vector graph(n, std::vector<std::pair<size_t, W>>{});
    for (const auto& [u, v, w]: edges) {
        graph[u].emplace_back(v, w);
        if (not is_directed) graph[v].emplace_back(u, w);
    }
    return graph;
}

__attribute__((constructor)) auto io_setup() noexcept {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);
    std::cerr << std::fixed << std::setprecision(10);
}

// Copyright (c) 2021 Mitama Lab | `tuple_scan`, `scan`, `in` are based on the code released under the ISC license. see
// https://opensource.org/licenses/ISC.
template<class Tp, std::size_t... I> inline decltype(auto) tuple_scan(Tp&, std::index_sequence<I...>);

inline auto scan = [](auto&... args) {
    return (..., [&] {
        if constexpr (is_tuple_like<std::decay_t<decltype(args)>>::value) {
            return tuple_scan(args, std::make_index_sequence<std::tuple_size_v<std::decay_t<decltype(args)>>>{});
        } else {
            return not (std::cin >> args).fail();
        }
    }());
};

template<class Tp, std::size_t... I> inline auto tuple_scan(Tp& tup, std::index_sequence<I...>) {
    return (... and scan(std::get<I>(tup)));
}

template<class T, class... Args> decltype(auto) inline in();

template<class Tp, std::size_t... I> inline auto tuple_in(std::index_sequence<I...>) {
    return std::tuple{ in<typename std::tuple_element_t<I, Tp>>()... };
}

template<class T, class... Args> decltype(auto) inline in() {
    if constexpr (sizeof...(Args) == 0) {
        if constexpr (is_tuple_like<T>::value) {
            auto t = tuple_in<T>(std::make_index_sequence<std::tuple_size_v<T>>());
            return t;
        } else if constexpr (is_1indexed<T>::value) {
            typename T::base x;
            scan(x);
            --x;
            return x;
        } else {
            T x;
            scan(x);
            return x;
        }
    } else {
        return std::tuple{ in<T>(), in<Args>()... };
    }
}

template<class T, class... size_t> inline auto in_vec(size_t&&... args) {
    return make_vector({ static_cast<usize>(args)... }, *in<T>);
}

inline constexpr char sep = ' ';
inline constexpr char eoln = '\n';
inline constexpr auto yes = "Alice";
inline constexpr auto no = "Bob";

inline auto print(){};

template<class T> inline auto print(T&&) -> void;

template<class Tp, std::size_t... I> inline auto tuple_print(Tp&& tp, std::index_sequence<I...>) -> void {
    (
        [&] {
            print(std::forward<decltype(std::get<I>(tp))>(std::get<I>(tp)));
            if constexpr (I + 1 != std::tuple_size_v<std::decay_t<Tp>>) print(sep);
        }(),
        ...);
}

template<class...> constexpr bool false_v = false;
template<class T> inline auto print(T&& x) -> void {
    if constexpr (is_printable<std::decay_t<T>>::value) {
        if constexpr (std::is_same_v<bool, std::decay_t<T>>) std::cout << (x ? yes : no);
        else std::cout << x;
    } else if constexpr (is_tuple_like<std::decay_t<T>>::value) {
        tuple_print(std::forward<T>(x), std::make_index_sequence<std::tuple_size_v<std::decay_t<T>>>());
    } else if constexpr (is_iteratable<T>::value) {
        for (auto it = std::begin(x); it != std::end(x); ++it) {
            print(std::forward<decltype(*it)>(*it));
            if (next(it) != std::end(x)) print(sep);
        }
    } else if (has_val<std::decay_t<T>>::value) {
        print(x.val());
    }
}

template<class T, class... Args> inline auto print(T&& t, Args&&... args) {
    print(std::forward<T>(t));
    print(sep);
    print(std::forward<Args>(args)...);
}

template<class... Args> inline auto println(Args&&... args) {
    print(std::forward<Args>(args)...);
    print(eoln);
}

template<class... Args> [[noreturn]] inline auto drop(Args&&... args) {
    println(std::forward<Args>(args)...);
    exit(0);
}

#define overload2(_NULL, _1, _2, name, ...) name
#define rep1(i, n) for (std::decay_t<decltype(n)> i = 0; i < (n); i++)
#define rep2(i, a, b) for (std::decay_t<decltype(b)> i = (a); i < (b); i++)
#define rep(...) overload2(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define LAMBDA(...) [&]([[maybe_unused]] const auto& _) { return __VA_ARGS__; }
#define LAMBDA2(...) [&](const auto& _1, const auto& _2) { return __VA_ARGS__; }
// }}}

using namespace std;

int main() {
    const auto n = in<u32>();
    u32 m = n;
    u32 nimber = 0;
    for (u32 p = 2; p * p < n; ++p) {
        u32 exp = 0;
        while (m % p == 0) {
            ++exp;
            m /= p;
        }
        nimber ^= exp;
    }
    if (m != 1) nimber ^= 1;
    println(nimber != 0);
}