这里提供两种做法。

Solution 1

比较无脑的二分答案+数位DP。

首先二分一个$n$，考虑如何计算不超过$n$的满足条件的数有多少。

这个问题可以用数位DP解决，设$f[i][j]$表示填了前$i$位，且第$i$位为$j$的方案数。注意最高位时特殊处理。

Solution 2

更推荐的做法，只需要基本计数原理即可。

考虑一个问题：恰好$L$为的满足条件的数有多少个？——略加思考应该能得到答案：$9\times 8^{L-1}$，因为最高位有$1\sim 9$可以填，之后每位可以填$8$种数字。

这样，就可以计算出最终答案的位数了，记这个位数为$L$。

对于每一位，都可以用类似的公式快速求出 如果这一位增大$1$，会有多少满足条件的数被囊括。如果这个个数超过了$k$，说明不能再增大$1$了，这时候就转而去枚举下一位。

需要注意，最高位应从$1$开始枚举（试探），其他位从$0$开始。