結果

問題 No.103 素因数ゲーム リターンズ
ユーザー omr14tomr14t
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
62,240 KB
testcase_01 AC 48 ms
62,768 KB
testcase_02 AC 47 ms
62,412 KB
testcase_03 AC 48 ms
62,604 KB
testcase_04 AC 49 ms
62,416 KB
testcase_05 AC 48 ms
62,972 KB
testcase_06 AC 48 ms
62,836 KB
testcase_07 AC 48 ms
62,912 KB
testcase_08 AC 48 ms
62,404 KB
testcase_09 AC 49 ms
62,252 KB
testcase_10 AC 48 ms
62,808 KB
testcase_11 AC 48 ms
63,340 KB
testcase_12 AC 48 ms
62,620 KB
testcase_13 AC 48 ms
62,124 KB
testcase_14 AC 47 ms
62,252 KB
testcase_15 AC 48 ms
62,456 KB
testcase_16 AC 48 ms
62,544 KB
testcase_17 AC 47 ms
62,224 KB
testcase_18 AC 48 ms
62,976 KB
testcase_19 AC 48 ms
62,672 KB
testcase_20 AC 48 ms
62,940 KB
testcase_21 AC 49 ms
62,280 KB
testcase_22 AC 48 ms
62,892 KB
testcase_23 AC 48 ms
63,160 KB
testcase_24 AC 49 ms
62,784 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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