#P3069. 水仙花数(100分)
-
2500ms
Tried: 342
Accepted: 43
Difficulty: 2
所属公司 :
华为od
水仙花数(100分)
题面描述:
水仙花数是指一个n位的正整数,其各位数字的n次方和等于该数本身。给定一个整数n(范围在3到7之间),以及一个整数m,请返回长度为n的第m个水仙花数。如果m大于水仙花数的个数,则返回最后一个水仙花数与m的乘积;如果输入不合法,则返回−1。例如,输入3和0时,输出153,因为153是一个3位数,且满足水仙花数的条件;而输入9和1时,输出-1,因为9超出范围。
思路:
直接枚举所有的n位数存起来判断即可
代码思路
-
输入合法性检查:
- 首先检查输入的n是否在3到7的范围内,如果不合法则直接返回−1。
-
水仙花数范围确定:
- 根据n的值,计算出所有可能的n位数的范围。最小值为10(n−1),最大值为10n−1。
-
预计算数字的n次方:
- 使用数组
p存储0到9的n次方,以便在后续计算时直接使用,避免重复计算。
- 使用数组
-
遍历n位数:
- 使用一个循环遍历所有n位数,并将每个数的每一位提取出来,计算它们的n次方和。
- 如果计算的和等于原数,则将该数存储到向量
a中。
-
输出结果:
- 根据索引m的值判断输出结果:
- 如果m小于水仙花数的数量,则输出对应的水仙花数。
- 如果m大于或等于数量,则输出最后一个水仙花数与m的乘积。
- 根据索引m的值判断输出结果:
cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int p[10]; // 存储0到9的n次方
signed main() {
int n, m;
cin >> n >> m;
// 特判
if (n < 3 || n > 7) {
cout << -1;
return 0;
}
vector<int> a;
int mn = (int)pow(10, n - 1); // n位数的最小值
int mx = (int)pow(10, n) - 1; // n位数的最大值
// 预处理i^n
for (int i = 0; i < 10; i++)
p[i] = (int)pow(i, n);
// 遍历所有n位数
for (int i = mn; i <= mx; i++) {
int temp = 0;
int x = i;
// 计算每位数字的n次方和
while (x) {
int s = x % 10; // 取当前位
x /= 10; // 去掉当前位
temp += p[s]; // 累加n次方
}
// 判断是否为水仙花数
if (temp == i)
a.push_back(temp);
}
// 输出结果
if (m >= a.size())
cout << m * a[a.size() - 1] << endl;
else
cout << a[m] << endl;
return 0;
}
python
import sys
def main():
# 读取所有输入并拆分
inputs = sys.stdin.read().split()
n = int(inputs[0])
m = int(inputs[1])
# 特判
if n < 3 or n > 7:
print(-1)
return
# 预处理0到9的n次方
p = [i ** n for i in range(10)]
mn = 10 ** (n - 1) # n位数的最小值
mx = 10 ** n - 1 # n位数的最大值
a = []
append = a.append # 局部变量加速
for i in range(mn, mx + 1):
temp = 0
x = i
while x > 0:
temp += p[x % 10]
if temp > i:
break # 提前终止,减少不必要的计算
x //= 10
if temp == i:
append(i)
# 输出结果
if m >= len(a):
print(m * a[-1]) # 返回最后一个水仙花数与m的乘积
else:
print(a[m]) # 返回第m个水仙花数
if __name__ == "__main__":
main()
java
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
// 特判
if (n < 3 || n > 7) {
System.out.println(-1);
return;
}
ArrayList<Long> a = new ArrayList<>();
long mn = (long) Math.pow(10, n - 1); // n位数的最小值
long mx = (long) Math.pow(10, n) - 1; // n位数的最大值
// 预处理0到9的n次方
long[] p = new long[10];
for (int i = 0; i < 10; i++) {
p[i] = (long) Math.pow(i, n);
}
// 遍历所有n位数
for (long i = mn; i <= mx; i++) {
long temp = 0;
long x = i;
// 计算每位数字的n次方和
while (x > 0) {
int s = (int) (x % 10); // 取当前位
x /= 10; // 去掉当前位
temp += p[s]; // 累加n次方
}
// 判断是否为水仙花数
if (temp == i) {
a.add(temp);
}
}
// 输出结果
if (m >= a.size()) {
System.out.println(m * a.get(a.size() - 1)); // 返回最后一个水仙花数与m的乘积
} else {
System.out.println(a.get(m)); // 返回第m个水仙花数
}
scanner.close(); // 关闭扫描器
}
}
题目内容
所谓水仙花数,是指一个n位的正整数,其各位数字的n次方和等于该数本身。
例如153是水仙花数,153是一个3位数,并且153=13+53+33。
输入描述
第一行输入一个整数n,表示一个n位的正整数。n在3到7之间,包含3和7。
第二行输入一个整数m,表示需要返回第m个水仙花数。
输出描述
返回长度是n的第m个水仙花数。
个数从0开始编号。
若m大于水仙花数的个数,返回最后一个水仙花数和m的乘积。
若输入不合法,返回−1。
样例1
输入
3
0
输出
153
说明
153是第一个水仙花数
样例2
输入
9
1
输出
-1
说明
9超出范围