いろんな人が $O(K\log K)$ で解いているので $O(K)$ で解けるんじゃない？という主張をします。(実際早くはなりません(元々がかなり早いので...))

そして当然constexprが乗ります！コンパイル時 $O(K)\ \ (\mathrm{maxK}=792)$ で実行時は出力するだけです arc099.contest.atcoder.jp 実際明快でわかりやすいC++の形です(第1144項目のすぬけ数で $10^{18}$ を超えるみたいです?)

本題

すぬけ数について、まずすぬけ関数 $f(n)$ を定義してみます。
$f(n):=\dfrac{n}{S(n)}\ (n\in\mathbb{N})$ とするのが自然で、この関数の極小値について考えていきます。

$S(n)$ について、 $S(n)\leqq S(n+1)\ (n\not\equiv9\pmod{10})\cdots(1)$ か $S(n)>S(n+1)\ (\textrm{otherwise})\cdots(2)$ が成り立ち、 $(2)$ のとき必ず $f(n)\lt f(n+1)$ です。
$(1)$ のときは、 $f(n)\leqq f(n+1)$ を変形すると $f(n)\leqq 1$ となってこれは $1\leqq n\leqq10$ です。

次に、 $(2)$ が成り立つ $n$ のみに定義域を絞ったときの $f(n)$ の極小値について考えます。
定義域は $n\equiv9\bmod{10}$ なので、 $f(n)\leqq f(n+10)$ について考えます。
すると、同様に考えて $n\equiv99\bmod{100}$ のときとそうでないときに分けられます。
以下 $n\equiv999\bmod{1000}$ 、 $n\equiv9999\bmod{10000}$ …と考えていくことができます。

ここで🎄気🎄になるのが、この論理の桁が上がっていくステップの中で、すぬけ数はどこで $(1)$ 側を満たすようになるのかということです。
よく考えると $(1)$ を満たすようになるところはすぬけ数のindexについて単調増加です。
つまり、あるところで $(1)$ が極小値でなくなったらこれから先は $(2)$ の形の極小値しか存在しないということです。

これを利用すると、「次の $(1)$ 型の極小値候補が極小でない」ときに「次の桁まで9を詰める」ことを決意すればいいことがわかります。

計算量ですが、次の $(1)$ 型が極小でないときだけ一回余分に計算しているので、（何も考えずに評価していますけど）たぶん（ $>1$ な）定数倍だけ余分な計算をしていると思います。
なのでたぶんこの答えは $O(K)$ です。