目录

一，完全数

HDU - 1406 完数

二，快乐数

力扣 202. 快乐数

数论里面有各种有趣的数。

一，完全数

HDU - 1406 完数

题目：

完数的定义：如果一个大于1的正整数的所有因子之和等于它的本身，则称这个数是完数，比如6，28都是完数：6=1+2+3；28=1+2+4+7+14。 

本题的任务是判断两个正整数之间完数的个数。 
Input
输入数据包含多行，第一行是一个正整数n，表示测试实例的个数，然后就是n个测试实例，每个实例占一行，由两个正整数num1和num2组成,(1<num1,num2<10000) 。 
Output
对于每组测试数据，请输出num1和num2之间（包括num1和num2）存在的完数个数。 
Sample Input
2
2 5
5 7
Sample Output
0
1

数学里面，一般都是叫完全数

偶完全数很好求，因为欧拉求出了所有的偶完全数，它们有共同的表达式：

t*(t-1)/2

其中t=2^p，满足p为素数且t-1为素数

这样，我们可以轻松求出，10000以内只有4个完全数：4,28,496,8128

这个时候，再用从num1到num2的循环就不合适了，最好是用常数时间的算法

有个地方需要注意，num1和num2的大小关系未知

代码：

      #include<iostream>
      using namespace std;
      int main()
      {
     	int a, b;
      	cin >> a;
     	while (cin >> a >> b)cout << ((a - 6)*(b - 6) <= 0) + ((a - 28)*(b - 28) <= 0) + ((a - 496)*(b - 496) <= 0) + ((a - 8128)*(b - 8128) <= 0) << endl;
     	return 0;
      }
  
 

这个代码，自然是0ms AC了

因为写的时候a和b是对称的，所以不需要额外判断a和b的大小

二，快乐数

A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers).

一个数的所有数字的平方和，替换这个数本身，一直循环这个过程，如果最后能变成1那么就是Happy Number

首先，很显然，经过几次替换之后就会得到一个小于200的整数，

然后找规律，我们发现不是快乐数的数都会陷入同一个循环，循环里面最小的数是4，我们用程序验证一下：

      #include<iostream>
      using namespace std;
      int f(long long n)//求平方和
      {
         if (n == 0)return 0;
         return f(n / 10) + (n % 10)*(n % 10);
      }
      int main()
      {
         for(int i=1;i<200;i++){
             int n=i;
             while(n!=1&&n!=4)n=f(n);
              cout<<n<<" ";
          }
         return 0;
      }
  
 

可以发现有32个1和167个4

力扣 202. 快乐数

题目：

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例: 

输入: 19
输出: true
解释: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路：

首先，很容易发现，所有的数经过若干次变换之后就最多三位数，而且不管再怎么变换都是最多三位数。

所以，所有的数最后都会进入循环。

其次，很容易发现，若干次变换之后一定会不超过162，而且不管再怎么变换都不超过162

只要枚举1到162经过若干次变换之后变成多少就行了。

结果是2个集合，一个是1，一个是{4,16,37......}

所以，所有的数经过若干次变换之后都会变成1或4

代码：

      class Solution {
      public:
     	bool isHappy(int n) {
     		if (n == 4)return false;
     		if (n == 1)return true;
     		int ans = 0;
     		while (n)
      		{
      			ans += n % 10 * (n % 10);
      			n /= 10;
      		}
     		return isHappy(ans);
      	}
      };
  
 

​

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/115706882