当前位置: 首页 > news >正文

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;
}
运行结果

 

http://www.xdnf.cn/news/649.html

相关文章:

  • JVM考古现场(二十二):降维打击·用二向箔优化内存模型
  • android如何在生产环境中做到详实的日志收集而不影响性能?
  • 算法之贪心算法
  • 【音视频】音视频FLV合成实战
  • Pikachu靶场-CSRF
  • Golang errors 包快速上手
  • 使用Qt multimedia模块实现简易的视频播放器
  • AI在能源消耗管理及能源效率提升中的核心应用场景及技术实现
  • Java性能剖析工具箱
  • 数据结构——反射、枚举以及lambda表达式
  • Qt 性能优化总结
  • Django 实现物联网管理系统的详细方案
  • 使用 OpenRewrite 简化 Java 和 SpringBoot 迁移
  • SDL基础
  • MATLAB 控制系统设计与仿真 - 34
  • 机器学习 | 细说Deep Q-Network(DQN)
  • 学习笔记十六——Rust Monad从头学
  • 【音视频】FLV格式分析
  • 让SQL飞起来:搭建企业AI应用的SQL性能优化实战
  • 2025年4月16日华为留学生笔试第二题200分
  • VS2022+QT环境配置及基本操作
  • Prometheus thanos架构
  • 2025年4月16日华为留学生笔试第三题300分
  • 自求导实现线性回归与PyTorch张量详解
  • Unity3d 6(6000.*.*)版本国区下载安装参考
  • 机器学习简介
  • python20-while和for in的美
  • 2025能源网络安全大赛CTF --- Crypto wp
  • visual studio 2022更改项目名称,灾难性故障(异常来自HRESULT)
  • 【Rust基础】使用Rocket构建基于SSE的流式回复