結果

問題 No.1946 ロッカーの問題
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:28:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,228 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 138,276 KB
最終ジャッジ日時 2025-03-31 17:30:11
合計ジャッジ時間 6,046 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split())) if m > 0 else []
    a_exists = [False] * (n + 1)
    for a in A:
        a_exists[a] = True

    # Precompute divisors for each x where d < x and d divides x
    divisors = [[] for _ in range(n + 1)]
    for d in range(1, n + 1):
        multiple = d * 2
        while multiple <= n:
            divisors[multiple].append(d)
            multiple += d

    # Precompute square checks
    is_square = [False] * (n + 1)
    for x in range(1, n + 1):
        s = int(x ** 0.5)
        if s * s == x:
            is_square[x] = True

    # Calculate c for each x
    c = [0] * (n + 1)
    for x in range(1, n + 1):
        t = 1 if is_square[x] else 0
        b = 1 if a_exists[x] else 0
        c[x] = (t - b) % 2

    # Calculate X for each x
    X = [0] * (n + 1)
    for x in range(1, n + 1):
        sum_d = 0
        for d in divisors[x]:
            sum_d = (sum_d + X[d]) % 2
        X[x] = (c[x] - sum_d) % 2

    # Count the number of students who skipped
    count = 0
    for x in range(1, n + 1):
        if X[x]:
            count += 1
    print(count)

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