UVA10591 Happy Number题解

LazYQwQ · 2021-10-02 16:43:57 · 题解

题意简述

• 输入一个数字，代表询问的次数
• 对于每一次询问，输入一个整数 N\ ( N <10^9)
• 算出它每位上数字的平方，再将得到的结果求和生成一个新数，对新数重复该操作，若最终生成数字 1 ,则称原数 N 是一个 Happy number，否则就是一个 Unhappy number 。

解题思路

• 最初觉得计算平方和的结果会非常大，需要很多的优化。
• 但实际上最大也就 9\times9^2=729
  ( N_{max} 有 9 个数位，每位最大为 9 因而 平方和最大为 9^2）
• 由此可见，除去 N 以外的别的数字都不会太大。打表啊
• 然后，配上这一段代码可以实现求出各数位平方和的过程：

  //预处理ans=n，防止覆盖原数，无法输出
  long long sum=0;//当前平方和
  while(ans>0) { //尚有数位未计算
  sum+=ans%10*ans%10;
  //对10取模后得到最小一位的值，平方后加入到平方和中
  ans/=10;//舍弃当前最小一位
  }
  if(sum==1) { //如果是happy number
  cout<<"Case #"<<i<<": "<<n<<" is a Happy number."<<endl;
  break;
  //跳出循环
  }

• 目前仅有一个问题尚未解决——若该数经过重复求平方和的操作无法到达 1 时，会进入死循环。
• 解决办法是，将每个已经求过平方和的数 i 的 vis_i 设为 1 ，再次遇到对应 vis_i 值为 1 的数时结束循环即可。

参考代码如下

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    long long t;//询问次数
    int sum;
    int ans;
    cin >> t;
    bool vis[800];
    for (long long i = 1; i <= t; i++) {
        cin >> n;//待判定的数字
        memset(vis, 0, 800);//重置vis数组
        ans = n;//防止n的原值被覆盖
        while (1) {
            sum = 0;

            while (ans >= 1) {
                sum += (ans % 10) * (ans % 10);
                ans /= 10;
            }//求出平方和

            if (sum == 1) {
                cout << "Case #" << i << ": " << n << " is a Happy number." << endl;
                break;
            }//得到了1即为Happy number
            if (sum == n or vis[sum]) {
                cout << "Case #" << i << ": " << n << " is an Unhappy number." << endl;
                break;//出现了循环
            } else if (sum != 1) {//没有循环也没有结束，准备继续求平方和
                vis[sum] = 1;//标记为已到
                ans = sum;//将平方和作为要继续被操作的数。
            }
        }
    }

    return 0;
}