結果

問題 No.103 素因数ゲーム リターンズ
ユーザー nadare
提出日時 2019-06-05 23:53:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,193 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-09-22 13:39:16
合計ジャッジ時間 2,280 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample RE * 5
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff #

from itertools import accumulate
from bisect import bisect, bisect_left
from functools import reduce
from itertools import accumulate, product
from operator import itemgetter, xor
from math import sqrt 

from fractions import gcd
from collections import Counter, deque, defaultdict
import sys
#input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N = int(input())
M = inpl()

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = 0
    return P


def get_factors(X):
    res = defaultdict(int)
    for i in range(bisect(P, sqrt(X))):
        while True:
            d, m = divmod(X, P[i])
            if m:
                break
            res[P[i]] += 1
            X = d
    if X != 1:
        res[X] += 1
    return res

def get_grundy(ddic):
    res = 0
    for v in ddic.values():
        res ^= v%3
    return res

P = primes(10**4)
Nim = [get_grundy(get_factors(m)) for m in M]
if reduce(xor, Nim):
    print("Alice")
else:
    print("Bob")

0