概要

各整数 \(A_i\) について、\(K\) で割った余りを調べ、余りが \(0\) のものだけを数えればよい問題です。
つまり、\(A_i \bmod K = 0\) である個数を数えるだけです。

考察

この問題で必要なのは、「ある整数が \(K\) の倍数かどうか」の判定です。

整数 \(a\) が \(K\) で割り切れる条件は、

\(a \% K = 0\)

であることです。
たとえば \(K = 3\) のとき、

• \(6 \% 3 = 0\) なので割り切れる
• \(-6 \% 3 = 0\) なので割り切れる
• \(0 \% 3 = 0\) なので割り切れる
• \(7 \% 3 \neq 0\) なので割り切れない

となります。

重要な気づき

各 \(A_i\) は独立に判定できます。
つまり、配列全体に対して複雑な処理は不要で、先頭から 1 個ずつ見ていけば十分です。

素朴なアプローチとの比較

たとえば、

• \(K\) の倍数をたくさん作って照合する
• \(A_i\) を何度も引き算して判定する

といった方法は、値の範囲が \(10^9\) まであるため非効率です。

一方で、剰余演算 % を使えば 1 回の判定で「割り切れるか」が分かります。
したがって、全要素を 1 回ずつ調べる \(O(N)\) の方法で十分高速です。

アルゴリズム

1. \(N, K\) を読み込む
2. \(N\) 個の整数 \(A_1, A_2, \ldots, A_N\) を読む
3. 各 \(A_i\) について、\(A_i \% K == 0\) ならカウントを 1 増やす
4. 最後にカウントを出力する

例えば、

• \(N = 5\)
• \(K = 4\)
• \(A = [8, 3, 0, -12, 7]\)

のとき、

• \(8 \% 4 = 0\) → 数える
• \(3 \% 4 \neq 0\) → 数えない
• \(0 \% 4 = 0\) → 数える
• \(-12 \% 4 = 0\) → 数える
• \(7 \% 4 \neq 0\) → 数えない

なので、答えは \(3\) です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 判定条件は a % K == 0 だけで十分です。

• 問題文にもある通り、負の数や \(0\) も含まれますが、この条件で正しく判定できます。

• \(N \leq 5 \times 10^5\) と大きめなので、コードでは sys.stdin.buffer.read() を使って高速に入力しています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2 + N]
    ans = sum(1 for a in A if a % K == 0)
    print(ans)

if __name__ == "__main__":
    main()

---

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