概要

\(N\) 種類のお菓子があり、それぞれ \(A_i\) 個ある。これらをお菓子を \(M\) 人で均等に分配したときの、1人あたりの個数と余りを求める問題。

考察

この問題は、各 \(A_i\) を \(M\) で割ったときの商と余りを求めるだけです。これは基本的な剰余演算（割り算）で求められます。

重要なのは、制約が大きいことです。\(N\) が最大 \(2 \times 10^5\)、\(A_i\) や \(M\) が最大 \(10^9\) なので、ループの中で複雑な処理を行ってしまうと時間がかかりすぎてしまう可能性があります。しかし、今回は単純に割り算を行うだけなので、各要素に対して定数時間で答えを求めることができます。

Python の // 演算子は商を、% 演算子は余りを求めることができます。これを使えば、各 \(A_i\) に対して \(A_i = M \times Q_i + R_i\) を満たす \(Q_i\) と \(R_i\) を簡単に求められます。

アルゴリズム

1. 入力から \(N\), \(M\) を受け取る。
2. 各お菓子の個数 \(A_i\) を順番に読み込みながら、以下を繰り返す：
   • \(Q_i = A_i // M\) （商）
   • \(R_i = A_i \% M\) （余り）
   • \(Q_i\) と \(R_i\) を出力する。

これは各要素に対して定数時間で処理できるので、十分高速です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力分のリストは必要だが、それ以外の追加的な記憶領域は定数）

実装のポイント

• Python では // で商、% で余りが求められる。

• 入力を一度に読み込んでリストにする（input().split()）ことで、後のループが簡潔になる。

• 特に工夫は必要なく、素直に割り算を行うだけでよい。

  ソースコード

N, M = map(int, input().split())
A = list(map(int, input().split()))

for a in A:
    Q = a // M
    R = a % M
    print(Q, R)

この解説は qwen3-coder-480b によって生成されました。