概要

\(N\) 個の整数 \(A_1, A_2, \ldots, A_N\) の中から、与えられた正の整数 \(K\) で割り切れるものの個数を求める問題です。

考察

ある整数 \(a\) が \(K\) で割り切れるかどうかを判定するには、余りを計算する演算子（%）を使用します。具体的には、a % K == 0 が真であれば \(a\) は \(K\) の倍数です。

この問題における重要なポイントは以下の 2 点です。

1. 負の数の扱い 問題文にある通り、\(-6\) は \(3\) で割り切れます。Python の % 演算子は、a % k の結果が常に \(0 \leq r < k\) の範囲（除数と同じ符号）になるように定義されています。そのため、a が負の数であっても、割り切れる場合には a % k は正確に 0 となり、特別な条件分岐なしで正の数と同様に扱うことができます。
2. 実行時間制限（高速な入出力） \(N\) が最大で \(5 \times 10^5\) と比較的大きいため、Python の標準的な input() 関数を \(N\) 回呼び出すと、入出力のオーバーヘッドで実行時間制限（TLE）に達する可能性があります。sys.stdin.read().split() を使って全ての入力を一度に読み込むことで、高速に処理を行うことができます。

アルゴリズム

1. 入力から \(N\) と \(K\) を取得します。
2. \(N\) 個の整数 \(A_i\) を順に確認します。
3. 各 \(A_i\) に対して、int(A_i) % K == 0 かどうかを判定します。
4. 条件を満たす（余りが 0 である）回数をカウントし、最終的なカウントを出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) 個の要素をそれぞれ 1 回ずつ確認するため、計算量は \(N\) に比例します。
• 空間計算量: \(O(N)\) sys.stdin.read().split() を使用して入力を全てメモリ上に保持するため、入力サイズに比例したメモリを消費します。

実装のポイント

• 高速な読み込み: 大量のアドホックな入力がある場合は、sys.stdin.read().split() でリスト化してからループを回すのが効率的です。

• 剰余演算: a % K == 0 というシンプルな式で、正の数・負の数・ゼロのすべてを正しく判定できます。

  • 例: -6 % 3 は 0

  • 例: 0 % 3 は 0

  • 例: 5 % 3 は 2

    ソースコード

import sys

def main():
    # 入力を標準入力から一括で読み込み、空白で分割します。
    # N が最大 5*10^5 と大きいため、sys.stdin.read().split() を使用して高速化します。
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 最初の2つの要素は N と K です。
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 割り切れる整数の個数をカウントする変数です。
    count = 0
    
    # A_1 から A_N までの各要素についてループを回します。
    # input_data[2] から input_data[2 + n - 1] までが A_i です。
    for i in range(2, 2 + n):
        # Python の % 演算子は、負の数に対しても a = k * q + r (0 <= r < k) となるように
        # 余りを計算するため、a が k で割り切れる場合は a % k が 0 になります。
        if int(input_data[i]) % k == 0:
            count += 1
            
    # 結果を出力します。
    print(count)

if __name__ == "__main__":
    main()

この解説は gemini-3-flash-thinking によって生成されました。