概要

\(N\) 人の従業員の報酬額が与えられたとき、報酬額が \(K\) の倍数である従業員の報酬額の合計を求める問題です。

考察

問題の整理

この問題で求められていることは以下の2ステップです： 1. 各従業員の報酬額 \(P_i\) が \(K\) の倍数かどうかを判定する 2. 条件を満たす報酬額をすべて合計する

倍数の判定方法

ある数 \(P_i\) が \(K\) の倍数であるかどうかは、余り（剰余） を使って判定できます。

\(P_i\) を \(K\) で割った余りが \(0\) であれば、\(P_i\) は \(K\) の倍数です。

例えば、\(K = 3\) のとき： - \(P_i = 6\) → \(6 \div 3 = 2\) 余り \(0\) → \(K\) の倍数 - \(P_i = 7\) → \(7 \div 3 = 2\) 余り \(1\) → \(K\) の倍数ではない

このアプローチで十分な理由

素朴に「すべての従業員を1人ずつ確認する」方法で十分間に合います。

• 従業員数 \(N\) は最大 \(2 \times 10^5\) 人
• 各従業員に対して、倍数判定（1回の割り算）を行うだけ
• 合計で約 \(2 \times 10^5\) 回の計算で済むため、時間制限内に収まる

特別な工夫やアルゴリズムは必要なく、シンプルな全探索で解けます。

アルゴリズム

1. \(N\) と \(K\) を入力から読み取る
2. 報酬額のリスト \(P\) を入力から読み取る
3. 合計を \(0\) で初期化する
4. 各報酬額 \(P_i\) について：
   • \(P_i \mod K = 0\)（\(P_i\) が \(K\) で割り切れる）なら、合計に \(P_i\) を加える
5. 最終的な合計を出力する

具体例

入力例: \(N = 5\), \(K = 3\), \(P = [6, 7, 9, 4, 12]\)

従業員	報酬額 \(P_i\)	\(P_i \mod 3\)	\(K\) の倍数？
1	6	0	✓
2	7	1	✗
3	9	0	✓
4	4	1	✗
5	12	0	✓

合計: \(6 + 9 + 12 = 27\)

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 人の従業員それぞれに対して、倍数判定（定数時間）と加算を行う
• 空間計算量: \(O(N)\)
  • 報酬額のリストを格納するために必要

実装のポイント

• 剰余演算子 %: Python では p % K == 0 で \(p\) が \(K\) の倍数かどうかを判定できます

• ジェネレータ式: sum(p for p in P if p % K == 0) のように書くと、条件を満たす要素の合計を1行で簡潔に表現できます

• 該当者がいない場合: 条件を満たす従業員が1人もいなければ、sum() は自動的に \(0\) を返すので、特別な処理は不要です

  ソースコード

N, K = map(int, input().split())
P = list(map(int, input().split()))

total = sum(p for p in P if p % K == 0)
print(total)

---

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