概要

与えられた \(N\) 個の整数それぞれについて、正の整数 \(K\) で割り切れるか（余りが 0 か）を判定し、該当する個数を数える問題です。
全要素を 1 回ずつ確認すれば解けます。

考察

重要なポイントは、「\(a\) が \(K\) で割り切れる」ことは \(a \bmod K = 0\) と同値、ということです。
したがって各 \(A_i\) に対して A_i % K == 0 を調べ、真ならカウントを増やせばよいです。

例えば、\(K=3\)、配列が \([6, -6, 7, 0]\) のとき：

• \(6 \% 3 = 0\) → 割り切れる
• \(-6 \% 3 = 0\) → 割り切れる
• \(7 \% 3 \neq 0\) → 割り切れない
• \(0 \% 3 = 0\) → 割り切れる（0 は任意の正の整数で割り切れる）

よって答えは 3 個です。

この問題では、各要素を一度見るだけで十分です。
制約 \(N \le 5 \times 10^5\) なので、全探索（1 回ループ）なら高速に間に合います。
逆に、不要に複雑な処理（ソートや二重ループ）を使うと無駄が増えます。

アルゴリズム

1. 入力から \(N, K\) と配列 \(A\) を受け取る。
2. カウンタ cnt = 0 を用意する。
3. 各要素 a について、a % k == 0 なら cnt += 1。
4. 最後に cnt を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（実装では配列を保持しているため。逐次処理にすれば \(O(1)\) も可能）

実装のポイント

• 負の数や 0 もそのまま % で判定して問題ありません。

• 入力サイズがやや大きいので、sys.stdin.buffer.read() を使った高速入力は有効です。

• arr = data[2:2+n] として、ちょうど \(N\) 個だけ取り出している点も安全です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n, k = data[0], data[1]
    arr = data[2:2 + n]

    cnt = 0
    for a in arr:
        if a % k == 0:
            cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。