概要

各種類のお菓子の個数 \(A_i\) を、人数 \(M\) で割ったときの「1人あたりに配れる個数（商）」と「余り」を、全種類 \(i=1..N\) について求めて出力する問題です。

考察

各種類のお菓子は「全員に同じ個数ずつ配る」ので、\(A_i\) を \(M\) 人で等分したときの結果がそのまま答えになります。
つまり、\(A_i = M \times Q_i + R_i\)（ただし \(0 \le R_i < M\)）となる \((Q_i, R_i)\) は、割り算の商と余りそのものです。

例えば \(M=4, A_i=14\) のとき、 - 1人あたり \(Q_i = 3\) 個配れる（\(3 \times 4 = 12\) 個配る） - 余りは \(R_i = 2\) 個（\(14-12=2\)） となります。

素朴に「配れる分を1個ずつ減らす」などのシミュレーションをすると、\(A_i\) が最大 \(10^9\) なので 1 種類だけでも非常に時間がかかり TLE になります。
しかし商と余りは割り算で一発で求まるため、各 \(A_i\) について \(O(1)\) で処理できます。

アルゴリズム

1. 入力で \(N, M\) と配列 \(A\) を受け取る。
2. 各 \(a \in A\) について、
   • \((q, r) = (a // M, a \bmod M)\) を求める（Python では divmod(a, M) が便利）。
3. 各行に q r を出力する。

計算量

• 時間計算量: \(O(N)\)（各 \(A_i\) につき割り算1回）
• 空間計算量: \(O(N)\)（出力をためて最後にまとめて出す場合）

実装のポイント

• Python では divmod(a, M) を使うと商と余りを同時に取得でき、実装が簡潔になります。

• \(N\) が最大 \(2 \times 10^5\) なので、入出力は sys.stdin.buffer.read() と "\n".join(...) でまとめて行うと高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    A = data[2:2+N]
    out = []
    for a in A:
        q, r = divmod(a, M)
        out.append(f"{q} {r}")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

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