結果

問題 No.1881 Everything is the same...
ユーザー gew1fw
提出日時 2025-06-12 16:11:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 884 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 71,940 KB
最終ジャッジ日時 2025-06-12 16:11:42
合計ジャッジ時間 4,550 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    # Precompute smallest prime factors (SPF) for numbers up to 1e5
    MAX = 10**5 + 1
    spf = list(range(MAX))
    for i in range(2, int(MAX**0.5) + 1):
        if spf[i] == i:
            for j in range(i*i, MAX, i):
                if spf[j] == j:
                    spf[j] = i

    # Read input
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))

    xor = 0
    for a in A:
        if a == 1:
            xor ^= 1
            continue
        # Factorize a
        factors = set()
        current = a
        while current != 1:
            p = spf[current]
            factors.add(p)
            while current % p == 0:
                current = current // p
        g = len(factors)
        xor ^= g

    if xor != 0:
        print("X")
    else:
        print("Y")

if __name__ == "__main__":
    main()
0