結果

問題 No.1946 ロッカーの問題
ユーザー gew1fw
提出日時 2025-06-12 18:59:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,193 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,696 KB
実行使用メモリ 156,128 KB
最終ジャッジ日時 2025-06-12 18:59:54
合計ジャッジ時間 5,932 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+M])) if M > 0 else []
    
    a_set = set(A) if M > 0 else set()
    
    # Precompute divisors for each k (d < k)
    divisors = [[] for _ in range(N+1)]
    for d in range(1, N+1):
        for k in range(2*d, N+1, d):
            divisors[k].append(d)
    
    # Precompute square numbers
    square = [False] * (N+1)
    for k in range(1, N+1):
        s = int(math.isqrt(k))
        if s * s == k:
            square[k] = True
    
    # Compute f(k) for each k
    f = [0] * (N+1)
    for k in range(1, N+1):
        if k in a_set:
            # f(k) = 1 if k is not square, else 0
            f[k] = 0 if square[k] else 1
        else:
            # f(k) = 1 if k is square, else 0
            f[k] = 1 if square[k] else 0
    
    x = [0] * (N+1)
    
    for k in range(1, N+1):
        sum_x = 0
        for d in divisors[k]:
            sum_x += x[d]
            sum_x %= 2
        x_k = (f[k] - sum_x) % 2
        x[k] = x_k
    
    print(sum(x))

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