概要

\(N\) 個の整数が与えられ、そのうち正の整数 \(K\) で割り切れるものの個数を数える問題です。

考察

• 整数 \(a\) が \(K\) で割り切れるかどうかは、\(a\) を \(K\) で割った余りが \(0\) かどうかで判定できます。つまり、\(a \mod K = 0\) であれば割り切れます。
• \(A_i\) には 負の数や \(0\) が含まれる点に注意が必要ですが、Python では負の数に対する剰余演算 % も正しく動作し、\(a \% K == 0\) で割り切れるかを正しく判定できます。
  • 例: \(-6 \% 3 = 0\)（割り切れる）、\(0 \% 5 = 0\)（割り切れる）
• この問題は各要素を 1 回ずつチェックするだけで解けるため、特別なアルゴリズムは不要です。素朴に全要素を走査して条件を満たすものを数えれば、\(N \leq 5 \times 10^5\) の制約下で十分間に合います。

具体例

\(N = 5, K = 3, A = [3, -6, 7, 0, 9]\) の場合：

答えは 4 です。

アルゴリズム

1. \(N\) と \(K\) を入力から読み取る。
2. \(N\) 個の整数 \(A_1, A_2, \ldots, A_N\) を読み取る。
3. 各 \(A_i\) について \(A_i \% K == 0\) かどうかを調べる。
4. 条件を満たすものの個数を数えて出力する。

コードでは、ジェネレータ式 sum(1 for a in A if a % K == 0) を使い、条件を満たす要素ごとに \(1\) を加算し、その合計を求めています。

計算量

• 時間計算量: \(O(N)\) — 各要素に対して剰余演算を 1 回行うだけです。
• 空間計算量: \(O(N)\) — 入力のリスト \(A\) を保持するために必要です。

実装のポイント

• Python の剰余演算と負の数: Python では \(a \% K\)（\(K > 0\)）の結果は常に \(0\) 以上 \(K\) 未満になります。そのため、\(a\) が負の数であっても a % K == 0 で割り切れるかを正しく判定できます。C++ や Java では負の数の剰余の扱いが異なるため、他の言語で解く場合は注意が必要です。

• ジェネレータ式の活用: sum(1 for a in A if a % K == 0) は、リストを新たに作らずにカウントするため、メモリ効率が良い書き方です。

  ソースコード

N, K = map(int, input().split())
A = list(map(int, input().split()))
print(sum(1 for a in A if a % K == 0))

この解説は claude4.6opus-thinking によって生成されました。