UVA - 10591 - Happy Number （STL）

浏览数：57 / 时间：2015年06月11日

UVA - 10591

Happy Number

Time Limit: 3000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

Submit Status

Description

Problem C	Happy Number
Time Limit	1 Second

Let the sum of the square of the digits of a positive integer S₀ be represented by S₁_. In a similar way, let the sum of the squares of the digits of S₁ be represented by S₂ and so on. If S_i = 1 for some i3 1, then the original integer S₀ 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 N smaller than 10⁹.

Output

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

Case #p: N is a Happy number.

Case #p: N is an Unhappy number.

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

Sample Input

Output for Sample Input

Case #1: 7 is a Happy number.

Case #2: 4 is an Unhappy number.

Case #3: 13 is a Happy number.

Problemsetter: Mohammed Shamsul Alam

International Islamic University Chittagong

Special thanks to Muhammad Abul Hasan

Source

Root :: Competitive Programming 2: This increases the lower bound of Programming Contests. Again (Steven & Felix Halim) :: Mathematics :: Cycle-Finding - Standard
Root :: Competitive Programming: Increasing the Lower Bound of Programming Contests (Steven & Felix Halim) :: Chapter 5. Mathematics :: Sequences and Number Systems :: Number Systems
Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: Volume 3. Brute Force :: Hashing / Sets
Root :: Competitive Programming: Increasing the Lower Bound of Programming Contests (Steven & Felix Halim) :: Chapter 5. Mathematics :: Cycle-Finding
Root :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: Mathematics :: Cycle-Finding :: Standard

Submit Status

思路：简单题，直接模拟过去即可，这里用set记录某个数出现没，出现了就可以判断出有环，即不是Happy Number，刚开始没想清循环结束条件，结果TLE了一次

AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

int main() {
	int N, cas = 1;
	scanf("%d", &N);
	while(N--) {
		int a, flag = 0;
		scanf("%d", &a);
		set<int> num;
		num.insert(a);
		int t = a; 
		while(1) {
			if(t == 1) {
				flag = 1;
				break;
			}
			int tmp = t;
			t = 0;
			while(tmp) {
				int b = tmp % 10;
				t += b * b;
				tmp /= 10;
			}
			if(num.count(t)) break;
			else num.insert(t);
		}
		
		if(flag) {
			printf("Case #%d: %d is a Happy number.\n", cas++, a);
		}
		else printf("Case #%d: %d is an Unhappy number.\n", cas++, a);
	}
	return 0;
}