13进制13位优美数计数最优算法与实现方案咨询

1. 原方案是否为最优解？ #

完全不是，甚至根本无法实际运行：

• 暴力枚举的总次数是13^13 ≈ 3e14，即便单次循环仅耗时1纳秒，完整跑完也需要至少300秒，实际运行耗时会达到数小时甚至更久，完全没有可行性。
• 你给出的代码还有逻辑错误：count_numbers |= (number++).is_beautiful()只会统计是否存在优美数，最终结果只会是0或1，你需要的是+=来累加计数。
• std::pow返回浮点数，用于整数循环边界判断可能存在精度误差，建议直接用整数常量计算。

2. 能否不用数组、仅用算术方法实现？ #

可以，但依然解决不了暴力枚举的性能问题：
你可以每次通过取模、除法操作直接提取各位数字求和，不需要额外数组存储：

bool is_beautiful(uint64_t num) {
    int sum_front = 0, sum_back = 0;
    // 先算最后六位的和
    for(int i=0; i<6; i++) {
        sum_back += num % 13;
        num /= 13;
    }
    // 跳过中间第7位
    num /=13;
    // 算前六位的和
    for(int i=0; i<6; i++) {
        sum_front += num %13;
        num /=13;
    }
    return sum_front == sum_back;
}

但即便优化了存储，3e14次枚举的量级还是完全不可接受。

3. 有没有专门的高效算法？ #

有，用动态规划（或者母函数）可以在毫秒级算出结果，完全不需要枚举：

问题本质拆解 #

13位13进制数的第7位（中间位）可以是0~12任意值，和前后六位的和是否相等完全无关，所以总优美数 = 13 × 「前六位数字和等于后六位数字和的方案数」。
而「前六位和等于后六位和的方案数」就是对每个可能的和s，计算「6位13进制数各位和为s的方案数f(s)」，再求所有s的f(s)²的总和即可。

动态规划计算f(s) #

定义dp[k][s]为k位13进制数，各位数字之和为s的总方案数：

• 初始状态：dp[0][0] = 1，0位数字和为0只有1种方案
• 转移方程：dp[k][s] = sum(dp[k-1][s - d])，其中d取0~12，且s-d ≥ 0
• 最终f(s) = dp[6][s]，s的取值范围是0~6×12=72，计算量极小。

示例实现代码 #

long long dp[7][73] = {0};
dp[0][0] = 1;
for(int k=1; k<=6; k++) {
    for(int s=0; s<=k*12; s++) {
        for(int d=0; d<=12 && s-d >=0; d++) {
            dp[k][s] += dp[k-1][s-d];
        }
    }
}
long long res = 0;
for(int s=0; s<=72; s++) {
    res += dp[6][s] * dp[6][s];
}
res *= 13; // 乘上中间位的13种可能

最终得到的res就是优美数的总个数，整个计算过程只需要几百次运算，性能是暴力枚举的数万亿倍。

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