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 是快乐数,则输出第一条消息;否则,输出第二条消息。
样例输入输出
输入:
3
7
4
13
输出:
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; }
运行结果