概要

\(K\) 個の商品の合計金額を計算し、その合計を \(M\) で割った余り（＝もらえるポイント）を求める問題です。

考察

求めたい値は \((L_1 + L_2 + \cdots + L_K) \bmod M\) です。

素朴には「全部足してから最後に \(\bmod M\) を取る」でも答えは出ます。しかし、一般に合計が非常に大きくなると（言語によっては）整数のオーバーフローが起きたり、無駄に大きな数を扱って計算が重くなることがあります。

ここで重要な性質として、次が成り立ちます： [ (a+b)\bmod M = \bigl((a\bmod M) + (b\bmod M)\bigr)\bmod M ] つまり、足し算の途中で何度 \(\bmod M\) を取っても最終結果は変わりません。

例えば \(M=7\)、価格が \([10, 5, 8]\) のとき、 - 合計は \(23\)、\(23\bmod 7 = 2\) - 途中で余りを取りながら計算すると
\(0 \to (0+10)\bmod 7=3 \to (3+5)\bmod 7=1 \to (1+8)\bmod 7=2\)
となり同じ結果 \(2\) になります。

この性質を使って「合計の余り」だけを逐次更新すれば、安全かつ高速に求められます。

アルゴリズム

1. 変数 total_mod を \(0\) で初期化する（これは「ここまでの合計を \(M\) で割った余り」）。
2. 各商品の価格 \(x\) について、次で更新する： \(total\_mod \leftarrow (total\_mod + x)\bmod M\)
3. 最後の total_mod を出力する。

計算量

• 時間計算量: \(O(K)\)（\(K\) 個を1回ずつ処理）
• 空間計算量: \(O(1)\)（余りを保持するだけ）

実装のポイント

• 入力サイズが最大 \(10^5\) なので、Pythonでは sys.stdin.buffer.read() のような高速入力を使うと安心です。
• 「合計を持つ」のではなく「合計の余りだけを持つ」ことで、途中の値が大きくならず安定します（他言語でも有効なテクニックです）。

ソースコード

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

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