Overview

A problem where you select only multiples of \(K\) from the given reward amounts and sum them up.

Analysis

In this problem, we need to determine whether each employee’s reward amount \(P_i\) is a multiple of \(K\), and find the sum of those that are.

The method of determination is to check whether the remainder of dividing \(P_i\) by \(K\) is \(0\). In programming, this can be expressed using the % operator as P_i % K == 0.

A straightforward approach is to iterate through the reward amounts of all employees in order, adding only those that satisfy the condition. This method works without any issues. Looking at the constraints, there can be up to \(N = 2 \times 10^5\) employees, so processing each element in constant time is sufficient to run within the time limit.

Also, note that the reward amounts and \(K\) can be up to \(10^9\), so there is a possibility of overflow with 32-bit integer types. However, in Python, arbitrary-precision integers are available by default, so this can be handled without concern.

Algorithm

1. Read the number of employees \(N\) and the multiple check value \(K\) from input.
2. Read each employee’s reward amount \(P_1, P_2, ..., P_N\) as an array.
3. For each reward amount, check whether \(P_i \% K == 0\).
4. If the condition is satisfied, add that reward amount to the running total.
5. Output the final total.

For example, given the following input:

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

In this case, the multiples of \(K=3\) are \(6, 9, 12\), and their sum \(6 + 9 + 12 = 27\) is the answer.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Since we examine each element exactly once, the time complexity is linear. Additionally, because we use an array to store the reward amounts, the space complexity is also linear.

Implementation Notes

• Use the modulo operator % to check for multiples.

• Initialize the sum variable to \(0\).

• In Python, there is no limit on integer size, so large values can be handled safely.

  Source Code

# 入力の読み込み
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)

This editorial was generated by qwen3-coder-480b.