概要

与えられた \(N\) 種類のお菓子の個数 \(A_i\) それぞれについて、人数 \(M\) で割った商（1人あたりの個数）と余り（配りきれずに余る個数）を求める問題です。

考察

問題文の条件「\(A_i = M \times Q_i + R_i\) かつ \(0 \le R_i < M\)」は、まさに整数の割り算における「商」と「余り」の定義そのものです。したがって、各 \(A_i\) を \(M\) で割るだけで答えを求めることができます。

例えば、\(A_i = 10\) 個のお菓子を \(M = 3\) 人で分ける場合、\(10 \div 3 = 3\) 余り \(1\) となるため、商は \(Q_i = 3\)、余りは \(R_i = 1\) となります。プログラミング言語に標準で用意されている割り算の演算子と、余りを求める演算子（剰余演算子）を使えば簡単に計算できます。

ただし、この問題ではお菓子の種類数 \(N\) が最大で \(2 \times 10^5\) と非常に大きくなる可能性があります。そのため、素朴に input() で1行ずつ読み込み、print() を \(N\) 回繰り返すような実装をすると、入出力の処理に時間がかかりすぎて実行時間制限超過（TLE）になってしまうことがあります。これを防ぐためには、入出力を一括で行う高速化の工夫が必要です。

アルゴリズム

1. 入力全体を一度に読み込み、空白や改行で区切って配列（リスト）に格納します。
2. 最初の2つの要素から \(N\) と \(M\) を取得します。
3. 続く \(N\) 個の要素（各 \(A_i\)）に対して順番に以下の処理を行います：
   • \(A_i\) を \(M\) で割った商 \(Q_i\) と余り \(R_i\) を計算する。
   • 計算結果を "Q_i R_i" という文字列の形式にして、出力用の配列に追加する。
4. すべての計算が終わったら、出力用の配列を改行文字で繋ぎ、一括で出力します。

計算量

• 時間計算量: \(O(N)\) 各 \(A_i\) に対して1回の割り算と余りの計算を行うだけであり、これらは定数時間 \(O(1)\) で完了します。それを \(N\) 回繰り返すため、全体の実行時間は \(O(N)\) となります。
• 空間計算量: \(O(N)\) 入力されたデータを一括で保持する配列と、出力結果を保持する配列を用意するため、\(O(N)\) のメモリを使用します。

実装のポイント

• divmod 関数の活用: Pythonには、商と余りを同時に計算して返してくれる divmod(a, b) という便利な組み込み関数があります。これを使うと q, r = divmod(A_i, M) のように1行で簡潔に書くことができます。

• 高速な入出力: sys.stdin.read().split() を使うことで、入力全体を非常に高速に読み込むことができます。また、出力時も print を何度も呼ぶのではなく、結果をリスト out に溜め込み、最後に '\n'.join(out) を使って1回の print で出力することで、大幅な時間短縮を実現しています。競技プログラミングにおいて大量の入出力を扱う際の定石です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    out = []
    for i in range(2, 2 + N):
        A_i = int(input_data[i])
        q, r = divmod(A_i, M)
        out.append(f"{q} {r}")
        
    print('\n'.join(out))

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。