UVA - 10591 - Happy Number （STL）

UVA - 10591 - Happy Number （STL）

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_1. 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

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.

 

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 
#include 
#include 
#include 
using namespace std;

int main() {
	int N, cas = 1;
	scanf("%d", &N);
	while(N--) {
		int a, flag = 0;
		scanf("%d", &a);
		set 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;
}