結果

問題 No.1881 Everything is the same...
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:50:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,738 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 79,004 KB
最終ジャッジ日時 2025-03-31 17:51:21
合計ジャッジ時間 5,538 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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

    max_val = 100000  # Maximum possible value of A_i as per the problem constraints

    # Precompute smallest prime factors (SPF) for sieve of Eratosthenes
    spf = list(range(max_val + 1))
    for i in range(2, int(max_val**0.5) + 1):
        if spf[i] == i:  # i is a prime number
            for j in range(i*i, max_val + 1, i):
                if spf[j] == j:
                    spf[j] = i

    total_sum = 0

    for a in A:
        # Compute phi(a)
        if a == 1:
            phi = 1
        else:
            # Factorize 'a' using the precomputed SPF
            factors = {}
            m = a
            while m > 1:
                p = spf[m]
                while m % p == 0:
                    factors[p] = factors.get(p, 0) + 1
                    m = m // p
            # Calculate phi using the formula phi(n) = n * product(1 - 1/p for p in prime factors)
            phi = 1
            for p, exp in factors.items():
                phi *= (p ** exp - p ** (exp - 1))

        # Factorize phi and sum the exponents
        if phi == 0:
            continue
        if phi == 1:
            sum_e = 0
        else:
            factors_phi = {}
            m = phi
            while m > 1:
                p = spf[m]
                while m % p == 0:
                    factors_phi[p] = factors_phi.get(p, 0) + 1
                    m = m // p
            sum_e = sum(factors_phi.values())

        total_sum += sum_e

    # Determine the winner based on the parity of total_sum
    if total_sum % 2 == 0:
        print("X")
    else:
        print("Y")

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