結果

問題 No.103 素因数ゲーム リターンズ
コンテスト
ユーザー walkre
提出日時 2016-07-09 02:14:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 1,572 bytes
コンパイル時間 1,580 ms
コンパイル使用メモリ 175,568 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 07:59:50
合計ジャッジ時間 2,644 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define show(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define show(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<62;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

//O(n^(1/2))
vector<long long int> prime_factor(long long int n){
    vector<long long int> res;
    for(int i=2; i*i<=n; ++i){
        while(n%i==0){
            res.push_back(i);
            n/=i;
        }
    }
    if(n!=1) res.push_back(n);
    return res;
};

void solve(){
    int grundy[10001]={};
    rep(i,2,10001){
        auto factor=prime_factor(i);
        set<int> s;
        for(int f:factor){
            s.insert(grundy[i/f]);
            if(i%(f*f)==0) s.insert(grundy[i/f/f]);
        }
        while(s.count(grundy[i])!=0) ++grundy[i];
    }

    int n,x=0;
    cin >> n;
    rep(i,0,n){
        int m;
        cin >> m;
        x^=grundy[m];
    }
    if(x) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}
0