Overview

This is a problem where you calculate the total price of \(K\) items and find the remainder when dividing that total by \(M\) (= the points you receive).

Analysis

The desired value is [ (L_1 + L_2 + \cdots + L_K) \bmod M ]

A naive approach of “add everything up and take \(\bmod M\) at the end” does produce the correct answer. However, in general, when the total becomes very large, integer overflow can occur (depending on the language), or handling unnecessarily large numbers can make computation slower.

An important property to note here is the following: [ (a+b)\bmod M = \bigl((a\bmod M) + (b\bmod M)\bigr)\bmod M ] In other words, taking \(\bmod M\) at any point during the addition does not change the final result.

For example, when \(M=7\) and the prices are \([10, 5, 8]\): - The total is \(23\), and \(23\bmod 7 = 2\) - Computing while taking the remainder along the way:
\(0 \to (0+10)\bmod 7=3 \to (3+5)\bmod 7=1 \to (1+8)\bmod 7=2\)
which gives the same result of \(2\).

Using this property, we can safely and efficiently compute the answer by incrementally updating only “the remainder of the running total.”

Algorithm

1. Initialize a variable total_mod to \(0\) (this represents “the remainder of the running total divided by \(M\)”).
2. For each item’s price \(x\), update as follows: [ total_mod \leftarrow (total_mod + x)\bmod M ]
3. Output the final value of total_mod.

Complexity

• Time complexity: \(O(K)\) (processing each of the \(K\) items once)
• Space complexity: \(O(1)\) (only storing the remainder)

Implementation Notes

• Since the input size can be up to \(10^5\), in Python it is advisable to use fast input methods such as sys.stdin.buffer.read().

• By maintaining “only the remainder of the total” instead of “the total itself,” intermediate values stay small and computation remains stable (this is a useful technique in other languages as well).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    K, M = data[0], data[1]
    prices = data[2:2+K]
    total_mod = 0
    for x in prices:
        total_mod = (total_mod + x) % M
    print(total_mod)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.