#858296 (C++23) No.103 素因数ゲームリターンズ

提出ソース

結果

問題	No.103 素因数ゲームリターンズ
コンテスト
ユーザー	AC2K
提出日時	2023-04-10 17:05:15
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2 ms / 5,000 ms
コード長	16,141 bytes
コンパイル時間	4,034 ms
コンパイル使用メモリ	261,788 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-10-06 02:58:49
合計ジャッジ時間	4,157 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 5
other	AC * 20

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:13:42: warning: 'grundy' is used uninitialized [-Wuninitialized]
   13 | constexpr ld eps = 1e-6;
      |                                          ^
main.cpp:9:9: note: 'grundy' declared here
    9 | using graph = std::vector<std::vector<int>>;
      |         ^~~~~~

ソースコード

raw source code

#line 2 "library/src/template.hpp"
#include<bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(x) (x).begin(),(x).end()
#define popcount(x) __builtin_popcount(x)
using i128=__int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = 1e9;
constexpr ll infl = 1e18;
constexpr ld eps = 1e-6;
const long double pi = acos(-1);
constexpr uint64_t MOD = 1e9 + 7;
constexpr uint64_t MOD2 = 998244353;
constexpr int dx[] = { 1,0,-1,0 };
constexpr int dy[] = { 0,1,0,-1 };
template<class T>constexpr inline void chmax(T&x,T y){if(x<y)x=y;}
template<class T>constexpr inline void chmin(T&x,T y){if(x>y)x=y;}
#line 4 "library/src/math/gcd.hpp"
namespace kyopro {
template <typename T> constexpr T _gcd(T a, T b) {
    assert(a >= 0 && b >= 0);
    if (a == 0 || b == 0) return a + b;
    int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b));
    a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b);
    while (a != b) {
        if (a == 0 || b == 0) {
            return a + b;
        }
        if (a > b) {
            a -= b;
            a >>= __builtin_ctzll(a);
        } else {
            b -= a;
            b >>= __builtin_ctzll(b);
        }
    }

    return a << d;
}
template <typename T> constexpr T ext_gcd(T a, T b, T& x, T& y) {
    x = 1, y = 0;
    T nx = 0, ny = 1;
    while (b) {
        T q = a / b;
        std::tie(a, b) = std::pair<T, T>{b, a % b};
        std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q};
        std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q};
    }
    return a;
}
};  // namespace kyopro
#line 2 "library/src/internal/barrett.hpp"
namespace kyopro {
namespace internal {
/// @brief barrett reduction
class barrett {
    using u32 = uint32_t;
    using u64 = uint64_t;

    u64 m;
    u64 im;

  public:
    explicit barrett() = default;
    explicit barrett(u64 m_)
        : m(m_), im((u64)(long double)static_cast<u64>(-1) / m_ + 1) {}

    inline u64 get_mod() const { return m; }
    constexpr u64 reduce(int64_t a) const {
        if (a < 0) return m - reduce(-a);
        u64 q = ((__uint128_t)a * im) >> 64;
        a -= m * q;
        if (a >= m) a -= m;
        return a;
    }
    constexpr u64 mul(u64 a, u64 b) const {
        if (a == 0 || b == 0) {
            return 0;
        }
        u64 z = a;
        z *= b;
        u64 x = (u64)(((__uint128_t)z * im) >> 64);

        u32 v = (u32)(z - x * m);

        if (v >= m) v += m;
        return v;
    }
};
};  // namespace internal
};  // namespace kyopro
#line 6 "library/src/internal/type_traits.hpp"
namespace kyopro {
namespace internal {
/// @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
template <typename... Args> struct first_enabled {};

template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
    using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
    : first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
    using type = T;
};

template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;

template <int dgt> struct int_least {
    static_assert(dgt <= 128, "digit have to be less or equals to 128");
    using type = first_enabled_t<std::enable_if<dgt <= 8, __int8_t>,
                                 std::enable_if<dgt <= 16, __int16_t>,
                                 std::enable_if<dgt <= 32, __int32_t>,
                                 std::enable_if<dgt <= 64, __int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t> >;
};
template <int dgt> struct uint_least {
    static_assert(dgt <= 128, "digit have to be less or equals to 128");
    using type = first_enabled_t<std::enable_if<dgt <= 8, __uint8_t>,
                                 std::enable_if<dgt <= 16, __uint16_t>,
                                 std::enable_if<dgt <= 32, __uint32_t>,
                                 std::enable_if<dgt <= 64, __uint64_t>,
                                 std::enable_if<dgt <= 128, __uint128_t> >;
};

template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;

template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;

template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;
};  // namespace internal
};  // namespace kyopro
#line 6 "library/src/internal/montgomery.hpp"
namespace kyopro {
namespace internal {
using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;
using i64 = int64_t;
using u128 = __uint128_t;
using i128 = __int128_t;
/// @brief MontgomeryReduction
template <typename T> class Montgomery {
    static constexpr int lg = std::numeric_limits<T>::digits;
    using LargeT = internal::double_size_uint_t<T>;
    T mod, r, r2, minv;
    T calc_inv() {
        T t = 0, res = 0;
        for (int i = 0; i < lg; i++) {
            if (~t & 1) {
                t += mod;
                res += static_cast<T>(1) << i;
            }
            t >>= 1;
        }
        return res;
    }

  public:
    Montgomery() = default;
    constexpr inline T get_mod() { return mod; }
    constexpr inline int get_lg() { return lg; }

    void set_mod(const T& m) {
        assert(m > 0);
        assert(m & 1);

        mod = m;

        r = (-static_cast<T>(mod)) % mod;
        r2 = (-static_cast<LargeT>(mod)) % mod;
        minv = calc_inv();
    }

    T reduce(LargeT x) const {
        u64 res =
            (x + static_cast<LargeT>(static_cast<T>(x) * minv) * mod) >> lg;

        if (res >= mod) res -= mod;
        return res;
    }

    inline T generate(LargeT x) { return reduce(x * r2); }

    inline T mult(T x, T y) { return reduce((LargeT)x * y); }
};
};  // namespace internal
};  // namespace kyopro
#line 6 "library/src/math/dynamic_modint.hpp"
namespace kyopro {
/// @note mod は32bitじゃないとバグる
template <int id = -1> 
class barrett_modint {
    using u32 = uint32_t;
    using u64 = uint64_t;

    using i32 = int32_t;
    using i64 = int64_t;
    using br = internal::barrett;

    static br brt;
    static u32 mod;
    u32 v;  // value
  public:
    static inline void set_mod(u32 mod_) {
        brt = br(mod_);
        mod = mod_;
    }

  public:
    explicit constexpr barrett_modint() : v(0) {
        assert(mod);
    }  // modが決定済みである必要がある
    explicit constexpr barrett_modint(i64 v_) : v(brt.reduce(v_)) {
        assert(mod);
    }

    u32 val() const { return v; }
    static u32 get_mod() { return mod; }
    using mint = barrett_modint<id>;

    // operators
    constexpr mint& operator=(i64 r) {
        v = brt.reduce(r);
        return (*this);
    }
    constexpr mint& operator+=(const mint& r) {
        v += r.v;
        if (v >= mod) {
            v -= mod;
        }
        return (*this);
    }
    constexpr mint& operator-=(const mint& r) {
        v += mod - r.v;
        if (v >= mod) {
            v -= mod;
        }

        return (*this);
    }
    constexpr mint& operator*=(const mint& r) {
        v = brt.mul(v, r.v);
        return (*this);
    }

    constexpr mint operator+(const mint& r) const { return mint(*this) += r; }
    constexpr mint operator-(const mint& r) const { return mint(*this) -= r; }
    constexpr mint operator*(const mint& r) const { return mint(*this) *= r; }

    constexpr mint& operator+=(i64 r) { return (*this) += mint(r); }
    constexpr mint& operator-=(i64 r) { return (*this) -= mint(r); }
    constexpr mint& operator*=(i64 r) { return (*this) *= mint(r); }

    friend mint operator+(i64 l, const mint& r) { return mint(l) += r; }
    friend mint operator+(const mint& l, i64 r) { return mint(l) += r; }
    friend mint operator-(i64 l, const mint& r) { return mint(l) -= r; }
    friend mint operator-(const mint& l, i64 r) { return mint(l) -= r; }
    friend mint operator*(i64 l, const mint& r) { return mint(l) *= r; }
    friend mint operator*(const mint& l, i64 r) { return mint(l) += r; }

    friend std::ostream& operator<<(std::ostream& os, const mint& mt) {
        os << mt.val();
        return os;
    }
    friend std::istream& operator>>(std::istream& is, mint& mt) {
        i64 v_;
        is >> v_;
        mt = v_;
        return is;
    }
    template <typename T> mint pow(T e) const {
        mint res(1), base(*this);

        while (e) {
            if (e & 1) {
                res *= base;
            }
            e >>= 1;
            base *= base;
        }
        return res;
    }
    inline mint inv() const { return pow(mod - 2); }

    mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
    mint operator/(const mint& r) const { return mint(*this) *= r.inv(); }
    mint& operator/=(i64 r) { return (*this) /= mint(r); }
    friend mint operator/(const mint& l, i64 r) { return mint(l) /= r; }
    friend mint operator/(i64 l, const mint& r) { return mint(l) /= r; }
};
};  // namespace kyopro
template <int id>
typename kyopro::barrett_modint<id>::u32 kyopro::barrett_modint<id>::mod;
template <int id>
typename kyopro::barrett_modint<id>::br kyopro::barrett_modint<id>::brt;

namespace kyopro {
template <typename T, int id = -1>
class dynamic_modint {
    using LargeT = internal::double_size_uint_t<T>;
    static T mod;
    static internal::Montgomery<T> mr;

  public:
    static void inline set_mod(T mod_) {
        mr.set_mod(mod_);
        mod = mod_;
    }

    static inline T get_mod() { return mod; }

  private:
    T v;

  public:
    dynamic_modint(T v_ = 0) {
        assert(mod);
        v = mr.generate(v_);
    }
    inline T val() const { return mr.reduce(v); }

    using mint = dynamic_modint<T, id>;
    mint& operator+=(const mint& r) {
        v += r.v;
        if (v >= mr.get_mod()) {
            v -= mr.get_mod();
        }

        return (*this);
    }

    mint& operator-=(const mint& r) {
        v += mr.get_mod() - r.v;
        if (v >= mr.get_mod) {
            v -= mr.get_mod();
        }

        return (*this);
    }

    mint& operator*=(const mint& r) {
        v = mr.mult(v, r.v);
        return (*this);
    }

    mint operator+(const mint& r) { return mint(*this) += r; }
    mint operator-(const mint& r) { return mint(*this) -= r; }
    mint operator*(const mint& r) { return mint(*this) *= r; }

    mint& operator=(const T& v_) {
        (*this) = mint(v_);
        return (*this);
    }

    friend std::ostream& operator<<(std::ostream& os, const mint& mt) {
        os << mt.val();
        return os;
    }
    friend std::istream& operator>>(std::istream& is, mint& mt) {
        T v_;
        is >> v_;
        mt = v_;
        return is;
    }
    template <typename P> mint pow(P e) const {
        assert(e >= 0);
        mint res(1), base(*this);

        while (e) {
            if (e & 1) {
                res *= base;
            }
            e >>= 1;
            base *= base;
        }
        return res;
    }
    mint inv() const { return pow(mod - 2); }

    mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
    mint operator/(const mint& r) const { return mint(*this) *= r.inv(); }
    mint& operator/=(T r) { return (*this) /= mint(r); }
    friend mint operator/(const mint& l, T r) { return mint(l) /= r; }
    friend mint operator/(T l, const mint& r) { return mint(l) /= r; }
};
};  // namespace kyopro
template <typename T, int id>
T kyopro::dynamic_modint<T, id>::mod;
template <typename T, int id>
kyopro::internal::Montgomery<T>
    kyopro::dynamic_modint<T, id>::mr;

/// @brief dynamic modint(動的modint)
/// @docs docs/math/dynamic_modint.md
#line 3 "library/src/math/miller.hpp"
namespace kyopro {
namespace miller {
using i128 = __int128_t;
using u128 = __uint128_t;
using u64 = uint64_t;
using u32 = uint32_t;

template <typename mint>
bool inline miller_rabin(u64 n, const u64 bases[], int length) {
    u64 d = n - 1;

    while (~d & 1) {
        d >>= 1;
    }

    u64 rev = n - 1;
    if (mint::get_mod() != n) {
        mint::set_mod(n);
    }
    for (int i = 0; i < length; i++) {
        u64 a = bases[i];

        if (n <= a) {
            return true;
        }
        u64 t = d;
        mint y = mint(a).pow(t);
        while (t != n - 1 && y.val() != 1 && y.val() != rev) {
            y *= y;
            t <<= 1;
        }

        if (y.val() != rev && (~t & 1)) return false;
    }
    return true;
}

constexpr u64 bases_int[3] = {2, 7, 61};  // intだと、2,7,61で十分
constexpr u64 bases_ll[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

/// @brief MillerRabinの素数判定
constexpr bool is_prime(u64 n) {
    if (n < 2) {
        return false;
    } else if (n == 2) {
        return true;
    } else if (~n & 1) {
        return false;
    }
    if (n < (1ul << 31)) {
        return miller_rabin<barrett_modint<-1>>(n, bases_int, 3);
    } else {
        return miller_rabin<dynamic_modint<u64, -1>>(n, bases_ll, 7);
    }
}
};  // namespace miller
};  // namespace kyopro
#line 6 "library/src/math/rho.hpp"
namespace kyopro {

///@brief 高速素因数分解(Pollard Rho法)
namespace rho {
using namespace std;
using i128 = __int128_t;
using u128 = __uint128_t;
using u64 = uint64_t;
using u32 = uint32_t;

template <typename mint> u64 find_factor(u64 n) {
    static u64 v = 20001;

    if (~n & 1uL) {
        return 2;
    }
    if (kyopro::miller::is_prime(n)) {
        return n;
    }

    if (mint::get_mod() != n) {
        mint::set_mod(n);
    }
    while (1) {
        v ^= v << 13, v ^= v >> 7, v ^= v << 17;
        u64 c = v;
        auto f = [&](mint x) -> mint { return x.pow(2) + c; };
        v ^= v << 13, v ^= v >> 7, v ^= v << 17;
        mint x = v;
        mint y = f(x);
        u64 d = 1;
        while (d == 1) {
            d = _gcd<long long>(abs((long long)x.val() - (long long)y.val()),
                                n);
            x = f(x);
            y = f(f(y));
        }
        if (1 < d && d < n) {
            return d;
        }
    }
    exit(0);
}
template <typename mint> std::vector<u64> rho_fact(u64 n) {
    if (n < 2) {
        return {};
    }
    if (kyopro::miller::is_prime(n)) {
        return {n};
    }
    std::vector<u64> v;
    std::vector<u64> st{n};
    while (st.size()) {
        u64& m = st.back();
        if (kyopro::miller::is_prime(m)) {
            v.emplace_back(m);
            st.pop_back();
        } else {
            u64 d = find_factor<mint>(m);
            m /= d;
            st.emplace_back(d);
        }
    }
    return v;
}
inline std::vector<u64> factorize(u64 n) {
    if (n < 2) {
        return {};
    }
    auto v = (n < (1uL << 31) ? rho_fact<dynamic_modint<u32>>(n)
                              : rho_fact<dynamic_modint<u64>>(n));
    std::sort(v.begin(), v.end());
    return v;
}

std::vector<pair<u64, int>> exp_factorize(u64 n) {
    std::vector<u64> pf = factorize(n);
    if (pf.empty()) {
        return {};
    }
    vector<pair<u64, int>> res;
    res.emplace_back(pf.front(), 1);
    for (int i = 1; i < (int)pf.size(); i++) {
        if (res.back().first == pf[i]) {
            res.back().second++;
        } else {
            res.emplace_back(pf[i], 1);
        }
    }

    return res;
}
};  // namespace rho
};  // namespace kyopro
#line 3 "main.cpp"
int main(){
    int m;
    scanf("%d", &m);
    int xor_sum = 0;
    
    constexpr int NIM_MAX = 30;
    int grundy[NIM_MAX + 1];
    for (int i = 1; i <= NIM_MAX; i++) {
        int transit = 0;
        if (i >= 1) {
            transit |= (1 << grundy[i - 1]);
        }
        if (i >= 2) {
            transit |= (1 << grundy[i - 2]);
        }
        grundy[i] = __builtin_ctz(~transit);
    }
    rep(i, m) {
        int n;
        scanf("%d", &n);
        auto pf = kyopro::rho::exp_factorize(n);
        for (const auto&[p,e]:pf){
            xor_sum ^= grundy[e];
        }
    }
    if (!xor_sum) {
        puts("Bob");
    } else {
        puts("Alice");
    }
}

yukicoder

結果

コンパイルメッセージ

ソースコード