結果

問題 No.103 素因数ゲーム リターンズ
ユーザー omr14tomr14t
提出日時 2021-06-22 14:37:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 89 ms / 5,000 ms
コード長 932 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 86,648 KB
実行使用メモリ 76,316 KB
最終ジャッジ日時 2023-09-05 16:04:02
合計ジャッジ時間 3,981 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 86 ms
76,116 KB
testcase_01 AC 85 ms
76,060 KB
testcase_02 AC 85 ms
76,036 KB
testcase_03 AC 83 ms
75,908 KB
testcase_04 AC 85 ms
76,316 KB
testcase_05 AC 85 ms
76,148 KB
testcase_06 AC 87 ms
76,040 KB
testcase_07 AC 85 ms
75,776 KB
testcase_08 AC 85 ms
76,060 KB
testcase_09 AC 86 ms
76,048 KB
testcase_10 AC 87 ms
76,132 KB
testcase_11 AC 87 ms
75,940 KB
testcase_12 AC 89 ms
76,064 KB
testcase_13 AC 86 ms
76,088 KB
testcase_14 AC 85 ms
76,108 KB
testcase_15 AC 85 ms
76,084 KB
testcase_16 AC 84 ms
76,088 KB
testcase_17 AC 83 ms
75,936 KB
testcase_18 AC 83 ms
76,116 KB
testcase_19 AC 85 ms
76,116 KB
testcase_20 AC 86 ms
76,180 KB
testcase_21 AC 83 ms
75,780 KB
testcase_22 AC 85 ms
76,272 KB
testcase_23 AC 83 ms
76,068 KB
testcase_24 AC 85 ms
75,972 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