概要

与えられた報酬額の中から \(K\) の倍数だけを選んで合計する問題。

考察

この問題では、各従業員の報酬額 \(P_i\) が \(K\) の倍数かどうかを判定し、該当するものの合計を求めます。

判定方法としては、\(P_i\) を \(K\) で割った余りが \(0\) であることを確認すればよいです。これはプログラミングにおいて % 演算子を使って P_i % K == 0 のように表現できます。

素朴な方法として、全員分の報酬額を順番に見て、条件に合うものだけを足していく方法があります。この方法は特に問題なく動作します。制約を見ると、最大で \(N = 2 \times 10^5\) 人いるため、各要素に対して定数時間で処理を行っても間に合います。

また、入力される報酬額や \(K\) は最大で \(10^9\) なので、32bit整数型ではオーバーフローする可能性がある点に注意が必要ですが、Pythonでは標準で任意精度整数が使えるため気にせず扱えます。

アルゴリズム

1. 入力から従業員数 \(N\) と倍数判定値 \(K\) を受け取る。
2. 各従業員の報酬額 \(P_1, P_2, ..., P_N\) を配列として読み込む。
3. 各報酬額について、\(P_i \% K == 0\) かどうかをチェックする。
4. 条件を満たす場合、その報酬額を合計に加算する。
5. 最終的な合計値を出力する。

例えば、入力が以下の場合：

N=5, K=3
P = [6, 7, 9, 10, 12]

このとき、\(K=3\) の倍数は \(6, 9, 12\) であり、これらを合計した \(6 + 9 + 12 = 27\) が答えとなります。

計算量

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

各要素を一度ずつ見ることになるので、時間計算量は線形です。また、報酬額を保持するために配列を使用しているため、空間計算量も線形になります。

実装のポイント

• 剰余演算子 % を用いて倍数判定を行う。
• 合計変数は初期値を \(0\) にしておくこと。
• Pythonでは整数の範囲に制限がないため、大きな値でも安全に扱える。

## ソースコード

```python
# 入力の読み込み
N, K = map(int, input().split())
P = list(map(int, input().split()))

# 合計を計算
total = 0
for p in P:
    if p % K == 0:
        total += p

# 結果の出力
print(total)

この解説は qwen3-coder-480b によって生成されました。