CodeForces 919-B/完美数问题有没有更有效的解决方案？

Question

那么，问题来了：

我们认为一个正整数是完美的，当且仅当它的数字之和恰好是 10。给定一个正整数 k，你的任务是找到第 k 个最小的完美正整数。

输入：单行正整数 k (1≤k≤10000)。

输出：一个数字，表示第 k 个最小的完美整数。

我对这个问题的解决方案是：

int main(){
    int k=0, m=19, c=0, sum=0;
    scanf("%d", &k);
    while(true){
        int n = m;
        sum = 0;
        while(n){
            sum+=n%10;
            n=n/10;
        }
        // printf("%d %d %d\n", n, sum, c);
        if(sum == 10) c++;
        if(c == k) break;
        m++;
    }
    printf("%d", m);
    return 0;
}

那么，有没有比这个更有效的解决方案呢？

我想了这个问题大约一个小时，然后决定用谷歌搜索答案。这个解决方案确实令我失望。我预计这个问题中会隐藏一些棘手的数学知识。

Answer 1

你的直觉是正确的，该解决方案是一种天真的暴力，适用于小情况，但随着

O(n²)

的增长而增长，并且随着

k

的增长而迅速减慢。有一个

O(1)

（恒定时间）解决方案：
这个问题之前曾在 math stackexchange 上提出过，并收到了一个漂亮的答案，概述了最佳解决方案here。