自幂数判断 题解

题目分析

自幂数（又称阿姆斯特朗数）的定义是：一个 $N$ 位数，其各位数字的 $N$ 次方之和等于该数本身。例如：

• $153$ 是三位数，$1^3 + 5^3 + 3^3 = 153$，是自幂数。
• $1634$ 是四位数，$1^4 + 6^4 + 3^4 + 4^4 = 1634$，也是自幂数。

题目要求我们连续判断 $M$ 个正整数是否为自幂数，如果是则输出 T，否则输出 F。数据范围：

• $M \le 100$
• 每个数 $n<10^8$ （最多 8 位数）

由于数据规模不大，我们只需对每个数按照定义进行验证即可。

解题思路

对于每一个待判断的整数 $n$，可以分三步完成判断：

1. 计算位数 $l$
   不断将 $n$ 除以 10，直到 $n$ 变为 0，累计除的次数即为位数。

2. 计算每位数字的 $l$ 次方之和 $\text{sum}$
   依次取出 $n$ 的每一位数字 $d$，计算 $d^l$ 并累加到 $\text{sum}$ 中。
   注意：应当使用原始的 $n$ 进行取位，但位数计算过程中会改变 $n$ 的值，因此在第一步之前先拷贝一份 $n$ 的值。

3. 比较 $\text{sum}$ 与 $n$
   若相等，输出 T，否则输出 F。

算法说明

• 计算位数：用 while 循环，每次将临时变量 t 除以 10，同时位数计数器加 1。
• 计算次方：为了精确，不使用浮点 pow 函数，而是用循环乘法完成整数次方运算。例如计算 $d^l$，可以用一个循环将 $d$ 自乘 $l$ 次。
• 取每一位：通过 t % 10 获取最低位数字，然后 t /= 10 去除最低位，直到 $t$ 变为 0。

整个过程完全基于整数运算，不会产生浮点误差。

时间复杂度分析

对于每个数字 $n$：

• 计算位数需要 $O(L)$ 次操作，$L$ 是位数。
• 计算每位数字的 $L$ 次方：共有 $L$ 个数字，每个数字需要 $O(L)$ 次乘法，这部分复杂度为 $O(L^2)$。
  由于 $n<10^8$，$L \le 8$，因此 $L^2 \le 64$，可以视为常数时间。
  总时间复杂度为 $O(M \times L^2) \approx O(M)$，完全可以满足题目要求。

代码实现

下面给出完整的 C++ 代码，并附有详细注释。
注意：参考代码中 using namespace std; 是不规范的写法，实际应为 using namespace std;（或去掉该行，改用 std::cout 等），下面代码已修正。

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int m;
6    cin >> m;                  // 读入待判断的数字个数
7
8    for (int i = 0; i < m; ++i) {
9        int n;
10        cin >> n;              // 读入当前待判断的数
11
12        // 1. 计算位数 l
13        int tmp = n, l = 0;
14        while (tmp > 0) {
15            tmp /= 10;
16            ++l;
17        }
18
19        // 2. 求各位数字的 l 次方之和 sum
20        int sum = 0;
21        tmp = n;               // 重置 tmp 为 n
22        while (tmp > 0) {
23            int d = tmp % 10;  // 取最低位数字
24            tmp /= 10;         // 移除最低位
25
26            // 计算 d 的 l 次方
27            int power = 1;
28            for (int j = 0; j < l; ++j) {
29                power *= d;
30            }
31            sum += power;      // 累加到 sum
32        }
33
34        // 3. 判断是否为自幂数并输出结果
35        if (sum == n)
36            cout << "T" << endl;
37        else
38            cout << "F" << endl;
39    }
40
41    return 0;
42}

代码解释

• 变量说明：tmp 用于暂存 n 的值，方便进行位数计算和取位而不会破坏原始数据。
• 计算位数：while (tmp > 0) 每次去除一位，l 记录位数。注意此处可以处理 n 为 0 的情况吗？题目输入为正整数，因此无需考虑 0。
• 计算次方：for (int j = 0; j < l; ++j) power *= d; 得到 d^l，这种方法简单且安全，不会产生浮点误差。
• 输出：题目要求每个结果占一行，所以使用 endl 换行（或 '\n' 均可）。

易错点与提示

• 避免使用 pow 函数：pow 返回浮点数，可能产生精度问题（如 pow(5, 3) 可能得到 124.999...），强转成 int 会出错。采用循环乘法可完全避免。
• 暂存原始数值：计算位数后 n 的副本已被修改，务必重新赋值再取位。
• 注意数据范围：$n<10^8$，位数最多 8 位，int 类型完全可以容纳。若使用更大的数据范围，需要考虑使用 long long。
• 输出格式：每个结果单独一行，大写字母 T 和 F。

总结

本题主要考察循环结构、位数提取以及幂运算的简单模拟。由于数据范围极小，直接暴力计算即可通过。理解自幂数的定义并细心实现每一位的处理是关键。