結果

問題 No.103 素因数ゲーム リターンズ
コンテスト
ユーザー hedwig100
提出日時 2022-09-24 18:52:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 5,000 ms
コード長 4,669 bytes
コンパイル時間 2,206 ms
コンパイル使用メモリ 205,396 KB
最終ジャッジ日時 2025-02-07 14:24:08
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_
void debug_out() {
    cerr << "\033[0m" << endl;
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H << ',';
    debug_out(T...);
}
#define debug(...) cerr << "\033[1;36m" << __func__ << ":L" << __LINE__ << " " << #__VA_ARGS__ << ":", debug_out(__VA_ARGS__)
#define dump(x) cerr << __func__ << ":L" << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define irep(i, n) for (int i = (int)(n)-1; i >= 0; --i)

using ll  = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

constexpr int INF        = 1000'000'000;
constexpr long long HINF = 4000'000'000000'000'000;
constexpr long long MOD  = 1000000007; // = 998244353;
constexpr double EPS     = 1e-4;
constexpr double PI      = 3.14159265358979;

#pragma region Macros
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '[';
    for (auto &e : v) {
        os << e << ',';
    }
    os << ']';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st) {
    os << '{';
    for (auto itr = st.begin(); itr != st.end(); itr++) {
        os << *itr << ',';
    }
    os << '}';
    return os;
}
template <typename K, typename V>
ostream &operator<<(ostream &os, const map<K, V> &mp) {
    os << '{';
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        os << itr->first << ": " << itr->second << ',';
    }
    os << '}';
    return os;
}

void yn(bool cond, string Yes = "Yes", string No = "No") {
    cout << (cond ? Yes : No) << '\n';
}

template <typename T>
bool chmax(T &x, const T &y) {
    return (x < y) ? (x = y, true) : false;
}

template <typename T>
bool chmin(T &x, const T &y) {
    return (x > y) ? (x = y, true) : false;
}

#pragma endregion

// OsaK
// n以下の整数の素因数分解を高速に行う.
// 制約: n >= 1
struct OsaK {
    int n;
    vector<int> smallest_prime_factor;

    OsaK(int n) : n(n) {
        smallest_prime_factor.assign(n + 1, -1);
    }

    // build
    // spf配列を用意する.
    // 計算量: O(nloglogn)
    void build() {
        long long i = 2;
        for (; i * i <= n; ++i) {
            if (smallest_prime_factor[i] < 0) {
                smallest_prime_factor[i] = i;
                for (long long p = i * i; p <= n; p += i) {
                    if (smallest_prime_factor[p] < 0) smallest_prime_factor[p] = i;
                }
            }
        }
        for (int j = i; j <= n; ++j) {
            if (smallest_prime_factor[j] < 0) smallest_prime_factor[j] = j;
        }
    }

    // factorize
    // 整数mを素因数分解する
    // 制約: 1 <= m <= n
    // 計算量: O(logm)
    template <typename T>
    vector<pair<T, int>> factorize(T m) {
        vector<pair<T, int>> ans;
        while (m > 1) {
            int p = smallest_prime_factor[m], e = 1;
            m /= p;
            while (p == smallest_prime_factor[m]) {
                ++e;
                m /= p;
            }
            ans.emplace_back(p, e);
        }
        return ans;
    }

    // count_factor
    // 整数mの約数の数を数える.
    // 制約: 1 <= m <= n
    // 計算量: O(logm)
    template <typename T>
    long long count_factor(T m) {
        auto ret      = factorize(m);
        long long ans = 1;
        for (const auto &p : ret) {
            ans *= (p.second + 1);
        }
        return ans;
    }
};

const int MAXN = 10006;
vector<int> grundy(MAXN, 0);
void solve() {
    OsaK osk(MAXN);
    osk.build();

    grundy[1] = 0;
    for (int i = 2; i < MAXN; i++) {
        set<int> s;
        auto f = osk.factorize(i);
        for (const auto &p : f) {
            if (p.second == 1) {
                s.insert(grundy[i / p.first]);
            } else {
                s.insert(grundy[i / p.first]);
                s.insert(grundy[i / p.first / p.first]);
            }
        }
        int g = 0;
        while (s.count(g))
            g++;
        grundy[i] = g;
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();
    int n;
    cin >> n;
    vector<int> M(n);
    rep(i, n) cin >> M[i];
    int ans = 0;
    for (int m : M)
        ans ^= grundy[m];
    yn(ans, "Alice", "Bob");

    return 0;
}
0