結果

問題 No.103 素因数ゲーム リターンズ
コンテスト
ユーザー omr14t
提出日時 2021-06-22 14:37:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 49 ms / 5,000 ms
コード長 932 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 63,340 KB
最終ジャッジ日時 2024-06-23 11:35:05
合計ジャッジ時間 2,408 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n = int(input())
M = tuple(map(int, input().split()))

m = 10000
min_facts = [0] * (m+1) # index値に対応する最小の素因数を求める
is_prime = [True] * (m+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, m+1):
    if not is_prime[i]:
        continue
    min_facts[i] = i

    for j in range(i*2, m+1, i):
        is_prime[j] = False
        if min_facts[j] == 0:
            min_facts[j] = i

def prime_factors(n):
    fact_counts = {}
    while n > 1:
        mf = min_facts[n]
        fact_counts.setdefault(mf, 0)
        fact_counts[mf] += 1
        n //= mf
    return fact_counts

grundy = [0]*(m+1)

grundy = 0
for m in M:
	facs = prime_factors(m)
	for _, count in facs.items():
		# 素因数毎のカウント
		# 3の倍数ではなかったら、1回の操作で3の倍数にできる。
		grundy ^= count%3

if grundy==0:
	# 先行が操作できないので
	print('Bob')
else:
	print('Alice')
0