結果

問題 No.103 素因数ゲーム リターンズ
コンテスト
ユーザー Fumiya Doi
提出日時 2025-12-06 11:51:43
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,792 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,925 ms
コンパイル使用メモリ 276,804 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-06 11:51:50
合計ジャッジ時間 5,507 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;

typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

ll llpow(ll a, ll t)
{
  ll res = 1;
  rep(i, t) res *= a;
  return res;
}

ll inf = std::numeric_limits<ll>::max();

using mint = modint;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pp = pair<ll, ll>;

// 0: l, 1: r, 2: u, 3: d
vector<ll> dx = {0, 0, -1, 1};
vector<ll> dy = {-1, 1, 0, 0};
vector<char> ds = {'L', 'R', 'U', 'D'};

// 素因数分解
// 460 = 2^2 x 5 x 23 の場合
// 返り値は {{2, 2}, {5, 1}, {23, 1}}
vector<pair<long long, long long>> prime_factorize(long long N)
{
  // 答えを表す可変長配列
  vector<pair<long long, long long>> res;

  // √N まで試し割っていく
  for (long long p = 2; p * p <= N; ++p)
  {
    // N が p で割り切れないならばスキップ
    if (N % p != 0)
    {
      continue;
    }

    // N の素因数 p に対する指数を求める
    int e = 0;
    while (N % p == 0)
    {
      // 指数を 1 増やす
      ++e;

      // N を p で割る
      N /= p;
    }

    // 答えに追加
    res.emplace_back(p, e);
  }

  // 素数が最後に残ることがありうる
  if (N != 1)
  {
    res.emplace_back(N, 1);
  }
  return res;
}

int main()
{
  ll n;
  cin >> n;
  vector<ll> ms(n);
  rep(i, n)
  {
    cin >> ms[i];
  }
  ll sum = 0;
  rep(i, n)
  {
    auto res = prime_factorize(ms[i]);
    for (auto p : res)
    {
      sum ^= p.second % 3;
    }
  }
  if (sum)
  {
    cout << "Alice" << endl;
  }
  else
  {
    cout << "Bob" << endl;
  }
}
0