\(x\) 以下の“Neq Numer” の数を \(f(x)\) とおくと、求める値は \(K \leq f(x)\) を満たす \(x\) の最小値です。 \(f(x)\) は \(x\) について単調であるため、 \(f(x)\) の計算が高速にできれば二分探索により求めることができます。

\(f(x)\) の計算については、 \(y < x + 1\) を満たす \(y\) のうち “Neq Number” であるものの数と考え、 \(y < x + 1\) が確定する桁が上から何桁目かで分けて求めます。これを \(k\) 桁目とすると、まず \(x\) の \(k\) 桁目より上の部分が “Neq Number” でない場合、このような \(y\) は \(0\) 個であり、”Neq Number” である場合は \(y\) の \(k\) 桁目より上の部分は \(x\) と同じです。

次に\(k\) 桁目以下として考えられるものの数を考えます。まず \(k\) 桁目の決め方は全探索により求められます。 \(k-1\) 桁目以下の桁の数字については \(0,1,\dots,9\) のうち、用いることができない数字は \(1\) 個上の桁の数字のみであるため、ちょうど \(9\) 通り考えられます。よって、 \(k\) 桁目として考えられるものの数を \(d\) と置くと、 \(y < x + 1\) が確定するのが上から \(k\) 桁目であるような “Neq Number” は \(d 9^k\)個と求まります。

これをすべての \(k\) について足し合わせれば求まるため、 \(f(x)\) の計算は \(O(\log x)\) 時間でできます。以上より答えの上界を \(M\) とすると、テストケースあたり \(O(\log^{2} M)\) 時間で計算できます。 \(M\) については \(18\) 桁の”Neq Number” の数は \(9^{18}\) 個であり \(K\) の上限より大きいため、 \(M\) として \(M=10^{18}\) などとすれば十分です。