自幂数判断 - C/C++ 代码实现

自幂数判断 - C/C++ 代码实现

时间限制： C/C++ 1000MS，其他语言 2000MS 内存限制： C/C++ 256MB，其他语言 512MB 分数： 25

描述

'自幂数'是指一个 N 位数，满足各位数字 N 次方之和是本身。例如，153 是 3 位数，其每位数的 3 次方之和，1^3 + 5^3 + 3^3 = 153，因此 153 是自幂数；1634 是 4 位数，其每位数的 4 次方之和，1^4 + 6^4 + 3^4 + 4^4 = 1634，因此 1634 是自幂数。

现在，输入若干个正整数，请判断它们是否是自幂数。

输入描述

输入第一行是一个正整数 M，表示有 M 个待判断的正整数。约定 1≤M≤100。 从第 2 行开始的 M 行，每行一个待判断的正整数。约定这些正整数均小于 10^8。

输出描述

输出 M 行，如果对应的待判断正整数为自幂数，则输出英文大写字母 'T'，否则输出英文大写字母'F'。

解法一：

对于每个待判断的正整数，首先将其转换为字符串，然后计算每位数字的 N 次方之和，最后判断是否等于原数。如果相等，则输出'T'，否则输出'F'。

时间复杂度分析：

对于每个待判断的正整数，需要计算每位数字的 N 次方之和，时间复杂度为 O(logN)。总共有 M 个待判断的正整数，所以总时间复杂度为 O(MlogN)。

解法二：

预先计算出 0~9 的 N 次方值，然后对于每个待判断的正整数，依次取出每位数字并计算其 N 次方值，最后求和。如果和等于原数，则输出'T'，否则输出'F'。

时间复杂度分析：

预先计算 0~9 的 N 次方值需要 O(10) 的时间复杂度。 对于每个待判断的正整数，需要取出每位数字并计算其 N 次方值，时间复杂度为 O(logN)。总共有 M 个待判断的正整数，所以总时间复杂度为 O(MlogN)。

综上所述，解法二更优。以下为解法二的代码实现。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool isSelfNum(int num, int N) {
    vector<int> powers(10);
    for (int i = 0; i < 10; i++) {
        powers[i] = pow(i, N);
    }
    int sum = 0;
    int temp = num;
    while (temp > 0) {
        int digit = temp % 10;
        sum += powers[digit];
        temp /= 10;
    }
    return sum == num;
}

int main() {
    int M;
    cin >> M;
    for (int i = 0; i < M; i++) {
        int num, N;
        cin >> num >> N;
        if (isSelfNum(num, N)) {
            cout << 'T' << endl;
        } else {
            cout << 'F' << endl;
        }
    }
    return 0;
}