Overview

Given \(N\) reward amounts \(P_i\), the problem asks us to extract only those that are multiples of \(K\) and find their sum.

Analysis

What we need is to check for each element whether “\(P_i\) is divisible by \(K\)”, and sum up only those that are divisible. In other words, the condition is \(P_i \bmod K = 0\).

In this problem, \(N \le 2 \times 10^5\), so simply examining each element once (a linear scan) is more than sufficient. Conversely, approaches like “enumerating multiples of \(K\) and matching” or “sorting and doing something clever” are unnecessary and only complicate the implementation (moreover, since \(K\) and \(P_i\) can be up to \(10^9\), an approach like enumerating multiples is not practical).

As a concrete example, when \(K=3\) and \(P=[1,3,4,6,9]\), the multiples are \(3,6,9\), so the sum is \(18\).

Algorithm

1. Read the input: \(N, K\) and the array \(P\)
2. Prepare a variable \(ans=0\) for the sum
3. For each \(p \in P\), do the following:
   • If \(p \% K == 0\), add \(p\) to \(ans\)
4. Finally, output \(ans\)

If no elements satisfy the condition, no additions occur, so \(0\) is output as-is.

Complexity

• Time complexity: \(O(N)\) (checking and adding each \(P_i\) once)
• Space complexity: \(O(N)\) (for storing the input array; with careful input reading, this can be reduced to nearly \(O(1)\))

Implementation Notes

• Since \(N\) can be up to \(2 \times 10^5\), in Python it is advisable to use fast input methods like sys.stdin.buffer.read().

• The check can be done in a single line: p % k == 0.

• The sum can be as large as approximately \(N \times 10^9\), but since Python integers have arbitrary precision, there is no need to worry about overflow.

  Source Code

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()

This editorial was generated by gpt-5.2-high.