解法

\(X\) 色のリストバンドを用意し一人あたり \(M\) 個のリストバンドを身につけるときにつくることができる色の多重集合の個数は \(\binom{X+M-1}{M}\) です。

したがって、\(\binom{X+M-1}{M} \ge N\) となる最小の自然数 \(X\) が答えです。 以降の説明では \(f(X)\coloneqq\binom{X+M-1}{M}\) とします。

\(X\) を \(1\) から順に線形探索していくと、答えが大きい（例えば \(N={10}^{18}\) 、 \(M=1\) ）場合に TLE してしまいます。また、 \(X\) を二分探索で求めようとすると、二項係数を求めるのに \(Θ(M)\) 時間かかり、 \(M={10}^{18}\) の場合などに TLE してしまいます。

ここで \(f\) の性質について考えると、\(f(X)=\frac{(X+M-1)!}{M!(X-1)!}=\frac{(X+M-1)(X+M-2) \cdots(X+1)X }{M!}\) であるため、おおよそ答えは \(\sqrt[M]{M!N}\) 程度、よりざっくりと見積もると\(\sqrt[M]{N}\) 程度であると予想ができます。

ここから \(M\) が大きければ \(X\) は小さくなる傾向が読み取れます。

\(N={10}^{18}\) 、 \(M=3\) の場合の答えは \(1,817,120\) であるため、以下のような方針を考えることができます。

1. \(M \le 2\) の場合

   クエリあたり \(O(1)\) または \(O(M\log{N})\) で答えを求める。

   二分探索を用いる場合には「答えは \(X\) 以上か？」という問いに対して \(O(M)\) 時間かけて二項係数を計算して判定します。

2. \(M \ge 3\) の場合

   \(X=1,2, \cdots\) と順に代入し、 \(f(X) \ge N\) が成立するかどうかを確かめる。

   \(K\) を自然数とし \(f(K)\) の値が分かっているとき、その値に \(\frac{K + M} {K}\) をかけることで \(f(K+1) \) の値が求められます。よってクエリあたり \(O(X)\) で答えを求めることができます。

これをそのまま計算すると、64bit整数を使用しかつ最終的な計算結果が64bit整数で表現可能な値であっても \(K+M\) をかけたときにオーバーフローする場合があります。128bit整数か多倍長整数を使用する方法もありますが、以下ではそれらを使わずにオーバーフローを回避する方法を紹介します。

オーバーフローの回避方法

\(\frac{K + M} {K}=1+\frac{M}{K}\) であることから以下の式が成立します。

\(f(K+1)=(1+\frac{M}{K})f(K)=f(K)+f(K)//K \times M+f(K)\%K \times M // K\)

ここで \(//\) は切り捨て除算、 \(\%\) は剰余演算を表します。

これは \(f(K+1) \lt N\) であれば64bit整数の範囲で計算途中もオーバーフローしないことが示せます。 \(f(K+1)\) が64bit整数の範囲で表現できない可能性についての判定は、\(N \le {10}^{18}\) であるので、 \({10}^{18}/ (K + M) \times K\) との大小を比較をすることで十分に判定できます。

なお、\(f(K) \) は \(K\) の倍数であるとは限らないため \(K\) で割ってから \(K+M\) をかける方法は誤りです。