概要

\(N\)種類のお菓子それぞれについて、\(M\)人で均等に分けたときの1人あたりの個数（商）と余りを求める問題です。

考察

この問題は、各お菓子の個数\(A_i\)に対して単純に\(M\)で割った商と余りを計算するだけで解けます。制約条件から、各\(A_i\)は最大\(10^9\)、\(M\)も最大\(10^9\)ですが、整数の除算と剰余演算は高速に実行できるため、素朴なアプローチでも十分に効率的です。

特に注意すべき点は、\(A_i\)が\(M\)より小さい場合でも、商が0、余りが\(A_i\)となる正しい結果が得られることです。また、\(A_i\)が0の場合も同様に、商0、余り0という正しい結果になります。

アルゴリズム

各\(A_i\)について以下の計算を行います： - 商 \(Q_i = A_i // M\) （整数除算） - 余り \(R_i = A_i \% M\) （剰余演算）

この計算は数学的な定義\(A_i = M \times Q_i + R_i\)（ただし\(0 \leq R_i < M\)）を満たします。Pythonの整数除算と剰余演算はこの条件を自動的に満たすため、特別な処理は必要ありません。

計算量

• 時間計算量: \(O(N)\)
  • \(N\)個のお菓子それぞれに対して定数時間で商と余りを計算するため
• 空間計算量: \(O(N)\)
  • 入力された\(N\)個のお菓子の個数を保存するため

実装のポイント

• 入力の読み取りにはsys.stdin.read().split()を使用して効率的に処理

• 各\(A_i\)に対して//演算子で商、%演算子で余りを計算

• 出力はフォーマット文字列f"{q} {r}"を使って簡潔に表現

• 大きな数値でもPythonの整数演算は正確に処理できるため、オーバーフローを心配する必要はありません

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    for a in A:
        q = a // m
        r = a % m
        print(f"{q} {r}")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。