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 S0 be represented by S1. In a similar way, let the sum of the squares of the digits of S1 be represented by S2 and so on. If Si = 1 for some i3 1, then the original integer S0 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 109.
?
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 - StandardRoot :: 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; }
?
?
?
?
?
?
?
?
?
?
?
?
?