MYOJ_11700(UVA10591)Happy Number(快乐数)(超快解法：图论思想解题)

2025/4/21 17:22:25 来源：https://blog.csdn.net/rstyduifudg/article/details/147312318 浏览: 次关键词：MYOJ_11700(UVA10591)Happy Number(快乐数)(超快解法：图论思想解题)

原题(English)

Let the sum of the square of the digits of a positive integer S0S0 be represented by S1S1. In a similar way, let the sum of the squares of the digits of S1S1 be represented by S2S2 and so on. If Si=1Si=1 for some i≥1i≥1, then the original integer S0S0 is said to be Happy number. A number, which is not happy, is called Unhappy number. For example 7 is a Happy number since 7 → 49 → 97 → 130 → 10 → 1 and 4 is an Unhappy number since 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.

Input

The input consists of several test cases, the number of which you are given in the first line of the input. Each test case consists of one line containing a single positive integer NN smaller than 109109.

Output

For each test case, you must print one of the following messages:

Case #p: NN is a Happy number.
Case #p: NN is an Unhappy number.

Here pp stands for the case number (starting from 1). You should print the first message if the number NN is a happy number. Otherwise, print the second line.

中文翻译

设正整数 S0 的各位数字的平方和为 S1。类似地，设 S1 的各位数字的平方和为 S2，依此类推。如果在某一步Si=1（其中 i≥1），则称原始整数 S0 为快乐数。不是快乐数的数称为不快乐数。例如，7 是一个快乐数，因为 7 → 49 → 97 → 130 → 10 → 1；而 4 是一个不快乐数，因为 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4。

输入

输入包含多个测试用例，测试用例的数量在第一行给出。每个测试用例包含一行，为一个小于 10^9 的正整数 N。

输出

对于每个测试用例，必须输出以下消息之一：

Case #p: N is a Happy number.
Case #p: N is an Unhappy number.

其中 p 表示用例编号（从 1 开始）。如果数字 N 是快乐数，则输出第一条消息；否则，输出第二条消息。

样例输入输出

输入：

输出：

Case #1: 7 is a Happy number.
Case #2: 4 is an Unhappy number.
Case #3: 13 is a Happy number.

思路：

因为他有多组数据，且数据可能达到10^9，所以肯定是不能用传统的循环，递推递归的，那就用

unordered_set<int>seen;

DDDD，哈希

STEP 1:定义(注意哈希不要在全局定义，不然还要清空，很麻烦)

STEP 2:判定函数，当n不是1且n未被见过时循环，首先将当前数字加入已见集合，定义一个数字用于计算数字各位平方和，然后提取每一位数字进行计算，获取最后一位数字进行平方累加，迭代更新n为平方和，跳出后判断最终结果是否为1

STEP 3:读写优化还是要开的，输入数量，for循环(为了方便按照题目要求输出，最好不用while(t--))先输出编号和输入数字，接着根据是否为快乐数来输出后面的

代码

#include<bits/stdc++.h>
using namespace std;
int t,n;
bool isHappy()
{unordered_set<int>seen;while(n!=1&&seen.find(n)==seen.end()){seen.insert(n);int sum=0;for(int i=n;i>0;i/=10){int digit=i%10;sum+=digit*digit;}n=sum;}return n==1;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;for(int i=1;i<=t;i++){cin>>n;cout<<"Case #"<<i<<": "<<n;if(isHappy()){cout<<" is a Happy number.\n";}else{cout<<" is an Unhappy number.\n";}}return 0;
}