色の数を \(X\) として、 \(K\) も与えられた場合にリストバンドの組み合わせが \(N\) 通り以上あるかどうかを判定できれば、 \(X\) についての二分探索で \(X\) の最小値が求まります。

リストバンドの組み合わせは \(\binom{M+X-1}{M}\) 通りです。よって、任意の二項係数について、その値が \(10^{18}\) 以上であるか判定し、 \(10^{18}\) 未満ならその値を計算することができれば十分です。

二項係数 \(\binom{n}{k}\) を計算するとき、 \(n-k< k\) の場合は \(\binom{n}{k}=\binom{n}{n-k}\) によって \(\binom{n}{n-k}\) の計算に帰着します。 \(\binom{100}{50}>10^{18}\) より、 \(k\geq 50\) のときはその値は \(10^{18}\) 以上です。 それ以外の場合は、分数 \(\dfrac{n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}\) を約分してから掛け合わせます。約分は、分子の因数と分母の因数の組 \(k^2\) 通りについて GCD で割る操作をすればできます。掛け合わせるときに \(10^{18}\) を超えるかどうかは、 \(a\times b\) のときに \(\lfloor 10^{18}/b\rfloor\) と \(a\) を比較することで判定できます。