ARC051 C - 掛け算

問題：C - 掛け算

解答：Submission #14204559 - AtCoder Regular Contest 051

解法：数列を昇順にし、a[0], a[1], ..., a[n-1]と並べる。a[0] * A ≧ a[n-1] となる場合、a[1] * A ≧ a[0] * Aである。つまり、一旦最小値をA倍した数が数列の最大値以上になると、それ以降は最小値をA倍したものが最大値以上になり続けることが分かる。

よって、数列の最小値のA倍が数列の最大値以上になるまでをシミュレーションし、数列の最大値以上になれば、その後の数列の各項にAが何回かけられるかが計算で決定できる。

注意点として、modをとる前の順序を出力しなければならないため、mod後の数列の順序にならないように気を付ける。
また、シミュレーション中は最大値を超えないため数がオーバーフローすることはないが、その後の数列計算ではオーバーフローに気を付ける。