求解任意位数的水仙花数

描述

输入数字位数 n，输出所有 n 位水仙花数（自幂数）。

解法1： 暴力枚举判断

1. n 有可能超过 unsigned long long 的表示范围
2. 时间复杂度 $O(10^n)$

结论：暴力不可取

解法2： 枚举组合 + 高精度 + 剪枝

第一步： 枚举组合

各位数字的 n 次方的和与其排列无关，因此与其枚举所有 n 位数字，不如枚举各位数字的组合。

各位数字的组合有如下特性：

1. 组合中有 n 个数字
2. 同一数字可以出现多次
3. 可以有序不重复地枚举组合

举例，当 n=2 时，枚举序列是这样的：

99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 
88, 87, 86, 85, 84, 83, 82, 81, 80, 
77, 76, ...

要有序枚举组合，可以用以下原则之一：

• 使组合成为一个非严格单调递减序列
• 使组合成为一个非严格单调递增序列

分别对应降序枚举和升序枚举。

显然用栈实现，要么用递归，要么手动维护。 为了减少函数调用的开销，这里选择手动维护。

第二步： 高精度

第一步给出了所有组合的迭代器，我们需要对每个组合计算各位数字的 n 次方的和，并检查其是否符合水仙花数的定义。

计算出和之后，只需保证和中的各数字出现次数与组合中的相同即可。当次数对应相同时，这个组合序列可以重新排列成对应的和，并且其他排列一定不是水仙花数。

大数字计算使用高精度实现，非常简单。 这里的 BInt 是 char 数组，每个 char 是一位十进制数字，倒序存储。 因为 $n*9^n < 10^{n+1}$，所以这里的所有 BInt 长度为 n+1.

在迭代组合时，需要维护一个 int cnt[10] 数组，记录该组合中各数字的出现次数，还有一个大整数 BInt sum, 记录各数字的 n 次方的和。

实现细节：

1. 迭代前计算 0～9 的 n 次方，保存在 BInt table[10]中。
2. 迭代时同步修改 cnt 数组
3. 迭代时同步修改 sum

第三步：剪枝

迭代通过依次产生第 i 位来实现。

在降序枚举时：

1. 如果当前的 sum 已经大于 $10^{n+1}$，那么就剪掉这个枝，因为继续产生下一位一定会增加 sum.
2. 如果当前的 sum 已经小于 $10^n$，那么就退出，因为下一个组合的 sum 一定比当前的小。

即使枚举组合，基数也是相当大的，剪枝可以剪掉绝大多数组合，大幅提升速度。

升序枚举也可应用这种策略，但因为有效组合主要集中在高位，剪枝效果并不好。

代码

地址： narcissus.cpp

代码中准备了一些调试函数，可自行插入调用，观察执行效果。

实测效果：计算21位水仙花数用时不超过6秒。

128468643043731391252
449177399146038697307
done