PTA 1117 数字之王 C++实现简易代码

给定两个正整数 N1<N2。把从 N1 到 N2 的每个数的各位数的立方相乘，再将结果的各位数求和，得到一批新的数字，再对这批新的数字重复上述操作，直到所有数字都是 1 位数为止。这时哪个数字最多，哪个就是“数字之王”。

例如 N1=1 和 N2=10 时，第一轮操作后得到 { 1, 8, 9, 10, 8, 9, 10, 8, 18, 0 }；第二轮操作后得到 { 1, 8, 18, 0, 8, 18, 0, 8, 8, 0 }；第三轮操作后得到 { 1, 8, 8, 0, 8, 8, 0, 8, 8, 0 }。所以数字之王就是 8。

本题就请你对任意给定的 N1<N2 求出对应的数字之王。

输入格式：

输入在第一行中给出两个正整数 0<N1<N2≤10^3，其间以空格分隔。

输出格式：

首先在一行中输出数字之王的出现次数，随后第二行输出数字之王。例如对输入 1 10 就应该在两行中先后输出 6 和 8。如果有并列的数字之王，则按递增序输出。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

10 14

输出样例：

2
0 8

解题思路：

模拟过程即可，但本题测试点有一点坑，尤其要注意输入是两个个位数的情况，处理不对会有两个测试点过不了

比如当n1为1 n2为5时候，则直接输出：

1

1 2 3 4 5

代码示例：

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n1, n2;
	cin >> n1 >> n2;

	vector<int> nums;
	for (int i = n1; i <= n2; i++) {
		nums.emplace_back(i);
	}

	//先判断n1到n2的数字序列是否都为个位数的情况，这种情况可以直接输出
	//比如n1为1 n2为5，则直接输出：
	//1
	//1 2 3 4 5
	if (n1 <= 9 && n2 <= 9) {
		cout << 1 << endl;
		for (int i = 0; i < nums.size(); i++) {
			if (i != 0) {
				cout << " ";
			}
			cout << nums[i];
		}
		return 0; //程序结束 不再执行后续语句
	}

	//再处理n1到n2的数字序列不都为个位数的情况
	vector<int> nums2; //用于存得到的每一批新的数字
	while (true) {
		for (int i = 0; i < nums.size(); i++) {
			string temp1 = to_string(nums[i]); //将nums中的每个数转化为字符串

			//将nums中的每个数的各位数的立方相乘
			int fact = 1;
			for (int j = 0; j < temp1.length(); j++) {
				fact *= (temp1[j] - '0') * (temp1[j] - '0') * (temp1[j] - '0');
			}

			//再将fact的各位数求和
			string temp2 = to_string(fact); //将fact转化为字符串
			int sum = 0;
			for (int k = 0; k < temp2.length(); k++) {
				sum += temp2[k] - '0';
			}

			nums2.emplace_back(sum); //存入处理后的数字
		}

		//判断nums2中的数是否都为个位数
		bool flag = true;
		for (int j = 0; j < nums2.size(); j++) {
			if (nums2[j] > 9) { //大于9就代表至少两位数了
				flag = false;
			}
		}

		if (flag == false) { //代表nums2中的数不都为个位数 需要再次处理
			nums = nums2;
			nums2.clear(); //清除掉nums2中的所有数
		}
		else {
			break; //只有当nums2中的数字都为个位数的情况下才会停止while循环
		}
	}

	//最后找出数字之王
	//multiset容器中允许有重复的数字 且存进去的数字会自动升序排序
	multiset<int> res;
	for (int i = 0; i < nums2.size(); i++) {
		res.insert(nums2[i]);
	}

	int max_val = 0; //找出最大出现次数
	for (auto p = res.begin(); p != res.end(); p++) {
		if (max_val < res.count(*p)) { //res.count(*p)用于查找*p的出现次数
			max_val = res.count(*p);
		}
	}
    
    //set容器会将存进去的数字去重处理（不会有重复的数字） 且存进去的数字会自动升序排序
	set<int> ans;
	for (auto p = res.begin(); p != res.end(); p++) {
		if (res.count(*p) == max_val) {
			ans.insert(*p); //将出现次数最多的数字(数字之王)都存入ans中
		}
	}

	//由于ans中的数字之王已经自动升序排序 那么直接按格式输出即可
	cout << max_val << endl;
	for (auto p = ans.begin(); p != ans.end(); p++) {
		if (p != ans.begin()) {
			cout << " ";
		}
		cout << *p;
	}

	return 0;
}