概要

\(N\) 人の従業員の報酬額 \(P_i\) のうち、指定された値 \(K\) の倍数であるものだけをすべて足し合わせた合計値を求める問題です。

考察

この問題を解くためのポイントは以下の2点です。

1. 倍数の判定方法 ある数 \(P_i\) が \(K\) の倍数であるかどうかは、プログラミングにおいては「\(P_i\) を \(K\) で割った余りが \(0\) であるか」を確認することで判定できます。多くの言語では % 演算子を用いて P_i % K == 0 という条件式で記述できます。

2. 計算量と数値の大きさ

   • 従業員数 \(N\) は最大で \(2 \times 10^5\) です。すべての従業員を 1 回ずつ確認する \(O(N)\) のアルゴリズムであれば、実行時間制限内に十分間に合います。
   • 報酬額 \(P_i\) は最大 \(10^9\)、人数 \(N\) は最大 \(2 \times 10^5\) であるため、合計値は最大で \(2 \times 10^{14}\) 程度になります。Pythonでは自動的に大きな整数（多倍長整数）が扱われるため問題ありませんが、C++などの言語では 64bit 整数型（long long など）を使用する必要があります。

アルゴリズム

1. 合計値を保持する変数 total_sum を \(0\) で初期化します。
2. 各従業員の報酬額 \(P_i\) を一つずつ順番に確認します。
3. もし \(P_i\) が \(K\) で割り切れる（P_i % K == 0）ならば、その値を total_sum に加算します。
4. すべての報酬額を確認し終えたあと、total_sum を出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) 個の要素を一度ずつ走査するため、入力の大きさに比例した時間で計算が完了します。
• 空間計算量: \(O(N)\) この実装では入力値をリスト（配列）にすべて格納しているため \(O(N)\) となります。なお、数値を一つずつ読み込みながら処理すれば \(O(1)\) に抑えることも可能です。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Pythonで input() を繰り返すと実行時間が長くなる場合があります。sys.stdin.read().split() を使って一括で入力を取得し、処理を高速化しています。

• 条件分岐: if p % k == 0: を使って、倍数のときのみ加算するようにしています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    p_list = map(int, input_data[2:])
    
    total_sum = 0
    for p in p_list:
        if p % k == 0:
            total_sum += p
            
    print(total_sum)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。