結果

問題 No.1946 ロッカーの問題
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:04:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 654 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 120,300 KB
最終ジャッジ日時 2025-03-20 21:04:46
合計ジャッジ時間 2,160 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    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]))
    
    s = [0] * (N + 1)
    for a in A:
        s[a] = 1
    
    sum_div = [0] * (N + 2)
    x = [0] * (N + 2)
    
    for k in range(1, N + 1):
        sum_so_far = sum_div[k]
        xk = (s[k] - sum_so_far) % 2
        x[k] = xk
        
        m = 2 * k
        while m <= N:
            sum_div[m] = (sum_div[m] + xk) % 2
            m += k
    
    ans = sum(1 - x[i] for i in range(1, N + 1))
    print(ans)
    
if __name__ == "__main__":
    main()
0