概要

与えられた \(N\) 個の報酬額 \(P_i\) のうち、\(K\) の倍数になっているものだけを取り出し、その合計を求める問題です。

考察

必要なのは「\(P_i\) が \(K\) で割り切れるか」を各要素について判定し、割り切れるものだけを足し合わせることです。
つまり条件は \(P_i \bmod K = 0\) です。

この問題では \(N \le 2 \times 10^5\) なので、全要素を 1 回ずつ見るだけの処理（線形走査）で十分間に合います。
逆に、例えば「\(K\) の倍数を列挙して照合する」「ソートして工夫する」などは不要で、実装が複雑になるだけです（また \(K\) や \(P_i\) が最大 \(10^9\) なので、倍数列挙のような方針は現実的ではありません）。

具体例として、\(K=3\), \(P=[1,3,4,6,9]\) のとき、倍数は \(3,6,9\) なので合計は \(18\) になります。

アルゴリズム

1. 入力として \(N, K\) と配列 \(P\) を受け取る
2. 合計用変数 \(ans=0\) を用意する
3. 各 \(p \in P\) について次を行う
   
   • もし \(p \% K == 0\) なら \(ans\) に \(p\) を加算する
4. 最後に \(ans\) を出力する
   該当する要素が 1 つもなければ加算が起きないため、そのまま \(0\) が出力されます。

計算量

• 時間計算量: \(O(N)\)（各 \(P_i\) を 1 回ずつ判定して加算）
• 空間計算量: \(O(N)\)（入力配列を保持するため。読み込み方を工夫すれば \(O(1)\) 近くにもできます）

実装のポイント

• \(N\) が最大 \(2 \times 10^5\) なので、Python では sys.stdin.buffer.read() のような高速入力を使うと安心です。

• 判定は p % k == 0 の 1 行で十分です。

• 合計は最大で \(N \times 10^9\) 程度になり得ますが、Python の整数は任意精度なのでオーバーフローを気にする必要はありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n, k = data[0], data[1]
    ps = data[2:2+n]
    ans = 0
    for p in ps:
        if p % k == 0:
            ans += p
    print(ans)

if __name__ == "__main__":
    main()

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