結果

問題 No.103 素因数ゲーム リターンズ
コンテスト
ユーザー uenoku
提出日時 2016-09-24 09:06:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 5,300 bytes
コンパイル時間 1,359 ms
コンパイル使用メモリ 121,620 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-17 20:31:19
合計ジャッジ時間 2,051 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include "math.h"
#include <algorithm>
#include <complex>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define ifor(i, a, b) for (int i = (a); i < (b); i++)
#define rfor(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long double ld;
typedef long long int lli;
typedef complex<double> P;
const double eps = 1e-11;
int vex[4] = {1, 0, -1, 0};
int vey[4] = {0, 1, 0, -1};
typedef vector<double> Vec;
typedef vector<int> vec;
typedef vector<Vec> MAT;
typedef vector<vec> mat;
lli MOD = 1000000007;
//Ax=bをとくAは正方行列
//rankA<=min(m,n)ならば配列０のvecが帰る


/*c++11から使える
for (auto itr = data.begin(); itr != data.end(); ++itr) {
        ans = ans * (itr->second + 1) % MOD;
    }*/
map<lli, lli> prime_factor(lli m)
{

    map<lli, lli> data;
    int a = 2;
    while (m >= a * a) {
        if (m % a == 0) {
            data[a]++;
            m /= a;
        } else {
            a++;
        }
    }
    data[m]++;
    return data;
}

Vec gauss_jordan(const MAT& A, const Vec& b)
{
    int n = A.size();
    MAT B(n, Vec(n + 1));
    rep(i, n) rep(j, n) B[i][j] = A[i][j];
    rep(i, n) B[i][n] = b[i];

    rep(i, n)
    {
        int pivot = i;
        for (int j = i; j < n; j++) {
            if (abs(B[j][i]) > abs(B[pivot][i]))
                pivot = j;
        }

        swap(B[i], B[pivot]);
        if (abs(B[i][i]) < eps)
            return Vec();
        //B_i_i成分が0であるつまり階数が
        for (int j = i + 1; j <= n; j++)
            B[i][j] /= B[i][i];
        rep(j, n)
        {
            if (i != j)
                for (int k = i + 1; k <= n; k++) {
                    B[j][k] -= B[j][i] * B[i][k];
                }
        }
    }
    Vec x(n);
    for (int i = 0; i < n; i++) {
        x[i] = B[i][n];
    }
    return x;
}
double det(const MAT& A)
{
    int n = A.size();
    MAT B(n, Vec(n));
    rep(i, n) rep(j, n) B[i][j] = A[i][j];
    double ans = 1;
    rep(i, n)
    {
        int pivot = i;
        for (int j = i; j < n; j++) {
            if (abs(B[j][i]) > abs(B[pivot][i]))
                pivot = j;
        }
        if (i != pivot)
            ans *= -1;
        swap(B[i], B[pivot]);
        if (abs(B[i][i]) < eps)
            return 0;
        ans *= B[i][i];
        for (int j = i + 1; j < n; j++)
            B[i][j] /= B[i][i];
        rep(j, n)
        {
            if (i != j)
                for (int k = i + 1; k < n; k++) {
                    B[j][k] -= B[j][i] * B[i][k];
                }
        }
    }
    return ans;
}

int rank(const MAT& A)
{
    int n = A.size();
    MAT B(n, Vec(n));
    rep(i, n) rep(j, n) B[i][j] = A[i][j];

    rep(i, n)
    {
        int pivot = i;
        for (int j = i; j < n; j++) {
            if (abs(B[j][i]) > abs(B[pivot][i]))
                pivot = j;
        }
        swap(B[i], B[pivot]);
        if (abs(B[i][i]) < eps)
            return i;
        for (int j = i + 1; j < n; j++)
            B[i][j] /= B[i][i];
        rep(j, n)
        {
            if (i != j)
                for (int k = i + 1; k < n; k++) {
                    B[j][k] -= B[j][i] * B[i][k];
                }
        }
    }
    return n;
}
lli euler(lli m)
{
    vector<int> p;
    lli M = m;
    for (int i = 2; i <= m; i++) {
        if (m % i == 0) {
            p.push_back(i);
            while (m % i == 0)
                m /= i;
        }
        if (M < i * i && p.size() == 0) {
            p.push_back(M);
            break;
        }
    }
    lli ans = M;
    rep(i, p.size())
    {
        //cout << p[i]<<endl;
        ans = ans * (p[i] - 1) / p[i];
    }
    return ans;
}
lli powm(lli a, lli p, lli mod)
{
    lli ans = 1;
    while (p > 0) {
        if (p & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        p >>= 1;
    }
    return ans % mod;
}
lli inv(lli a, lli mod)
{
    return powm(a, euler(mod) - 1, mod);
}
lli inv(lli a)
{
    return powm(a, MOD - 2, MOD);
}
lli gcd(lli A, lli B)
{
    if (A % B == 0)
        return B;
    else
        return gcd(B, A % B);
}
mat mul_mat_mod(mat A, mat B, lli m)
{
    int n = A.size();
    mat C(n, vec(n));
    rep(i, n) rep(j, n) rep(k, n)
    {
        C[i][j] += A[i][k] * B[k][j] % m;
        C[i][j] %= m;
    }
    return C;
}
mat pow_mat(mat A, lli p, lli mod)
{
    int n = A.size();
    mat B = mat(n, vec(n));
    while (p > 0) {
        if (p & 1) {
            B = mul_mat_mod(A, B, mod);
        }
        A = mul_mat_mod(A, A, mod);
        p >>= 1;
    }
    return B;
}
lli comb(lli a, lli b)
{
    lli ans = 1;
    rep(i, b)
    {
        ans = ans % MOD * (a - i) % MOD * inv(b - i) % MOD;
    }
    return ans;
}
int near(double a)
{
    int b = (int)a;
    if (a - b > 0.5)
        b++;
    return b;
}

int main()
{
    int N, M;
    int ans = 0;
    cin >> N;
    rep(i, N)
    {
        cin >> M;
        map<lli, lli> data = prime_factor(M);
        for (auto itr = data.begin(); itr != data.end(); ++itr) {
            ans ^= (itr->second) % 3;
        }
    }
    if (ans)
        cout << "Alice" << endl;
    else
        cout << "Bob" << endl;
}
0