結果

問題 No.103 素因数ゲーム リターンズ
コンテスト
ユーザー yuuki arisawa
提出日時 2021-03-24 01:06:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 8,726 bytes
コンパイル時間 3,163 ms
コンパイル使用メモリ 209,916 KB
最終ジャッジ日時 2025-01-19 21:20:52
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// set<int, greater<int> > s;
// vector<int> v(N);
// for(int i =0;i<N;i++){
//   cin >> v.at(i);
// }
// single line with multi param
// vector of vector
//   vector<vector<int>> data(row,vector<int>(col));
// for(int row=0;row<N;row++){
//    for(int col=0;col<N;col++){
//      cin >> data[row][col];
//  }}
//  cout << std::fixed << std::setprecision(9) <<ret << endl;
// sort(A.begin(),A.end(),greater<int>());
// long long s = accumulate(A.begin(),A.end(),(long long)0);
// unordered_map<string,int>m({{"SUN",1},{"MON",2},{"TUE",3},{"WED",4},{"THU",5},{"FRI",6},{"SAT",7}});
// max({A,B,C});
// S.substr(i,2)=="RS"
// SS.erase (std::remove(SS.begin(), SS.end(), 'A'), SS.end()); //delete string
// char c = 'a';string({c});
// transform(ret.begin(),ret.end(),ret.begin(),::toupper);
// to be review
// * abc139_b
// * abc099_b
// * abc090_a
// * abc062_a
// * abc032_a
// * abc030_b
// * abc027_b
// * abc021_a
// * abc018_a
// * abc182_c
// * abc181_c
// * abc175_c
// * abc170_c
// * abc161_c
// * abc154_c space O(1)
// * abc151_c
// * abc147_c
// * abc113_c
// * abc123_c
// * abc115_c
// * abc153_d
// * abc120_c
// * abc081_b
// * arc108_b
// * abc157_c
// * sumitrust2019_c
// * abc165_c
// * abc031_d
// * abc023_d
// * agc021_a
// * abc139_b
// * agc041_a
// * abc120_c
// * arc073_c
// * arc069_c
// * agc014_a
// * abc103_c
// * agc017_a
// * agc040_a
// * agc028_a
// * agc008_a
// * agc007_a
// * abc116_c
// * abc064_c
// * agc016_a
// * agc034_a
// * cf16_b
// * abc188_e
// * abc052_c
// * abc110_d
// * abc142_d
// * arc067_c
// * abc146_c
// * abc061_c
// * abc114_d
// * abc114_c
// * arc032_a
// * arc034_c
// * aoj_2706
// * aoj_DSL_3_D
// * abc172_c
// * arc084_c
// * arc110_a
// * apc001_a
// * abc124_d
// * arc106_b
// * abc157_d
// * agc046_a
// * abc185_d
// * arc044_a
// * abc046_a
// * abc039_c
// * arc107_b
// * arc054_a
// * abc136_d
// * arc051_a
// * abc180_d
// * abc190_d
// * abc121_d
// * abc038_c
// * abc130_d
// * abc127_d
// * arc018_b
// * arc001_c
// * digitalarts2012_a
// * code-festival-2015-quala_c
// * abc192_d
// * srm_StockHistory
// * dp_i
// * srm_BinaryFlips
// * abc088_c
// * past202004-open_d
// * past201912-open_e
// * past201912-open_h
// * past202005-open_g
// * abc161_d
// * dp_a
// * dp_e
// * past202005-open_h
// * tdpc_a
// * past202004-open_h
// * past201912-open_g
// * past202005-open_c
// * abc179_c
// * arc107_a
// * abc098_c
// * abc194_c
// * abc194_e
// * abc146_c
// * past202004_g
// * typical_algorithm_b
// * past201912_k
// * past202005_i
// * abc195_d
// * past202005_m
// * past201912_j
// * abc099_c
// * abc196_d
// * arc115_a
// * arc115_c
// check list
// * variable range
// * immeditate value is int range(accumulate)
// * index range(0 origin or 1 origin)
// * input is complete?
// * unued input
// * loop initial value
// * check variable range maximum and minimum
// * misunderstand input(node Edge and node Vertex)
// * check que front and back
// * check not using INT_MAX but LONG_LONG_MAX
// * modify element in graph retrieval
// * dp initial value, max index+1
// * return value could be negative?(initial value 0 to INT_MIN)
// * if value is gradually increasing, use bin search
// * Time complexity limit 10^8
#include <bits/stdc++.h>
using namespace std;

// https://www2.slideshare.net/Roadagain/ss-71620380
// https://github.com/kurokoji/.cpp-Template/blob/master/template/template.cpp
#define int long long
// check over flow
// assert(a<LONG_LONG_MAX-b)
// a+b
// assert(a<LONG_LONG_MAX/b)
// a*b
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
    }
} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define RALL(v) rbegin(v), rend(v)
// #define X real()
// #define Y imag()

/* debug */
#define debug(x)                  \
    cerr << #x << ":" << x << " " \
         << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
// const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) { return y >= 0 && x >= 0 && y < H && x < W; }
template <class T = int>
inline T in() {
    T x;
    cin >> x;
    return (x);
}
inline vs split(const string& t, char c) {
    vs v;
    stringstream s(t);
    string b;
    while (getline(s, b, c))
        if (b != "") v.eb(b);
    return v;
}
inline string join(const vs& ss, char c) {
    string s;
    for (int i = 0; i < (int)ss.size(); i++) {
        s += (i != (ll)ss.size() - 1 ? ss[i] + c : ss[i]);
    }
    return s;
}
template <typename T>
inline bool chmin(T& a, const T& b) {
    if (a > b) a = b;
    return a > b;
}
template <typename T>
inline bool chmax(T& a, const T& b) {
    if (a < b) a = b;
    return a < b;
}

template <typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

template <typename T, typename S>
inline void print(const pair<T, S>& p) {
    cout << p.first << " " << p.second << endl;
}
template <typename T>
inline void print(const T& x) {
    cout << x << '\n';
}
template <typename T, typename S>
inline void print(const vector<pair<T, S>>& v) {
    for (auto&& p : v) print(p);
}
template <typename T>
inline void print(const vector<T>& v, string s = " ") {
    for (int i = 0; i < v.size(); i++) cout << v[i] << (i != (long long)v.size() - 1 ? s : "\n");
}
template <typename T>
inline void print(const T& b, const T& e, string s = " ") {
    for (auto i = b; i != e; i++) print(*i);
}
template <typename T>
void pprint(T const& a) {
    std::cout << " " << a;
}
template <typename... Args>
void pp(Args... args) {
    using swallow = std::initializer_list<int>;
    (void)swallow{(void(pprint(args)), 0)...};
    cout << endl;
}

template <typename T>
inline unordered_map<T, int> counter(const vector<T>& v) {
    unordered_map<T, int> m;
    for (int i = 0; i < v.size(); i++) m[v[i]]++;
    return m;
}
inline unordered_map<char, int> counter(const string& v) {
    unordered_map<char, int> m;
    for (int i = 0; i < (long long)v.size(); i++) m[v[i]]++;
    return m;
}
// clang-format on
/* }}} */

string enc(long long i, long long j) { return to_string(i) + " " + to_string(j); }
uint64_t combinations2(uint64_t n, uint64_t k) {
    uint64_t r = 1;
    for (uint64_t d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

#define REP(i, n) for (int i = 0; (i) < (int)(n); ++(i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++(i))
#define REP_R(i, n) for (int i = (int)(n)-1; (i) >= 0; --(i))
#define REP3R(i, m, n) for (int i = (int)(n)-1; (i) >= (int)(m); --(i))
#define ALL(x) ::std::begin(x), ::std::end(x)
using namespace std;

const string FIRST = "Alice";
const string SECOND = "Bob";
/*  prime_factor(n)
    入力：整数 n
    出力：nの素因数分解
    計算量：O(√n)前後
*/
template <typename T>
map<T, T> prime_factor(T n) {
  map<T, T> ret;
  for (T i = 2; i * i <= n; i++) {
    T ex = 0;// 指数
    // 割れる限り割り続ける
    while (n % i == 0) {
      ex++;
      n /= i;
    }
    // その結果を push
    ret[i] = ex;
  }
  // 最後に残った数について
  if (n != 1) ret[n] = 1;
  return ret;
}
int g2(int m){
  //cout << "g2:" << m << endl;
  // if(m<=0)return 0;
  // int ret=0;
  // for(int i=1;i<=min(m,(int)2);i++){
  //   ret^=m%3;//g2(m-i);
  // }
  return m%3;
}
int g1(int m){
  int ret=0;
  for(const auto [p,f]:prime_factor(m)){
    ret^=g2(f);
  }
  return ret;
}
bool solve(int n, const vector<int64_t>& a) {
  int ret = 0;
  REP(i,n)
    ret = ret^g1(a[i]);
  return !(ret==0);
}

// generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator)
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    constexpr char endl = '\n';
    // failed to analyze input format
    // TODO: edit here
    int n;
    cin >> n;
    vector<int64_t> a(n);
    REP (i, n) { cin >> a[i]; }
    auto ans = solve(n, a);
    cout << (ans ? FIRST : SECOND) << endl;
    return 0;
}
0