結果

問題 No.103 素因数ゲーム リターンズ
ユーザー 303Yuyu
提出日時 2021-03-12 00:10:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,791 bytes
コンパイル時間 1,711 ms
コンパイル使用メモリ 172,300 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 11:00:33
合計ジャッジ時間 2,732 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using ld = long double;
using vld = vector<ld>;
using vb = vector<bool>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

template <class T> bool chmin(T& a, T b) {
    if(a > b) { a = b; return true; }
    else return false;
}

template <class T> bool chmax(T& a, T b) {
    if(a < b) { a = b; return true; }
    else return false;
}

template <class T> ostream& operator<<(ostream& s, const vector<T>& a) {
    for(auto i : a) s << i << ' ';
    return s;
}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

// 素因数分解
// nの(素因数、指数)のペアを返す。計算量はO(√nlogn)
vector<pair<ll, ll>> prime_factorize(ll n) {
    vector<pair<ll, ll>> ret;
    for(ll i = 2; i*i <= n; ++i) {
        if(n % i != 0) continue;
        ll ex = 0;
        while(n % i == 0) {
            ++ex;
            n /= i;
        }
        ret.push_back({i, ex});
    }
    if(n > 1) ret.push_back({n, 1});
    return ret;
}

// https://yukicoder.me/problems/no/103
void solve() {
    ll n;
    cin >> n;
    ll x = 0;
    while(n--) {
        ll m;
        cin >> m;
        vpll p = prime_factorize(m);
        for(auto i : p) x ^= i.second % 3;
    }
    string s;
    if(x) s = "Alice";
    else s = "Bob";
    cout << s << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}
0