CodeForces 919B完美数问题是否存在更高效解法？

问题定义 #

我们将一个正整数定义为完美数，当且仅当其各位数字之和恰好为10。给定正整数k（1≤k≤10000），需找到第k小的完美正整数。

输入：单行输入一个正整数k。
输出：对应的第k小完美整数。

现有暴力遍历解法 #

你提供的C语言暴力遍历代码如下：

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;
}

该解法从19开始逐个检查每个数的各位和，直到找到第k个符合条件的数，虽然逻辑简单，但效率较低——尤其是当k较大时，需要遍历大量无关数字。

更高效的解法 #

1. 步长优化遍历法 #

观察规律可知：各位和为10的数必然满足 n ≡ 1 mod 9（因为各位和模9等于数本身模9，10 mod 9 = 1）。因此我们可以只遍历所有9x+1形式的数，步长设为9，大幅减少需要检查的数字数量。

代码实现：

#include <stdio.h>

int digit_sum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int k;
    scanf("%d", &k);
    int count = 0;
    int num = 19; // 第一个符合条件的数
    while (1) {
        if (digit_sum(num) == 10) {
            count++;
            if (count == k) {
                printf("%d\n", num);
                break;
            }
        }
        num += 9; // 仅遍历9x+1形式的数
    }
    return 0;
}

该解法的循环次数约为暴力法的1/9，效率显著提升。

2. 组合数学构造法（最优解） #

通过组合数学的隔板法，我们可以直接构造出第k个完美数，无需任何遍历检查，效率为O(结果位数)，适合所有k≤10000的场景。

核心思路：

• 各位和为10的m位数，等价于求解a₁+a₂+…+aₘ=10（a₁≥1，其余aᵢ≥0，且每个aᵢ≤9）的非负整数解，按数字从小到大排序后对应第k个数。
• 先确定结果的位数m，再逐位计算每一位的数字，通过组合数快速定位第k个解的位置。

代码实现：

#include <stdio.h>

long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    k = k < n - k ? k : n - k; // 取较小值减少计算量
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - k + i) / i;
    }
    return res;
}

int main() {
    int k;
    scanf("%d", &k);
    
    // 确定结果的位数m
    int m = 2;
    long long total = 0;
    while (1) {
        long long cnt = comb(m + 8, 9) - 1; // m位数的完美数数量
        if (total + cnt >= k) {
            k -= total; // 剩余k在m位数中的位置
            break;
        }
        total += cnt;
        m++;
    }
    
    int remaining_sum = 10;
    int remaining_digits = m;
    long long result = 0;
    
    // 逐位构造数字
    for (int i = 0; i < m; i++) {
        int start = (i == 0) ? 1 : 0; // 首位从1开始，其余从0开始
        for (int d = start; d <= 9; d++) {
            if (d > remaining_sum) break;
            int new_sum = remaining_sum - d;
            int new_digits = remaining_digits - 1;
            long long cnt;
            if (new_digits == 0) {
                cnt = (new_sum == 0) ? 1 : 0;
            } else {
                cnt = comb(new_sum + new_digits - 1, new_digits - 1);
            }
            if (cnt < k) {
                k -= cnt;
            } else {
                result = result * 10 + d;
                remaining_sum = new_sum;
                remaining_digits = new_digits;
                break;
            }
        }
    }
    
    printf("%lld\n", result);
    return 0;
}

该解法直接通过数学计算生成结果，是效率最高的方案。

内容的提问来源于stack exchange，提问作者BugHunter