原题目
对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 1，就称该数为幸福数。1 是一个幸福数。此外，例如 19 经过 1 次迭代得到 82，2 次迭代后得到 68，3 次迭代后得到 100，最后得到 1。则 19 就是幸福数。显然，在一个幸福数迭代到 1 的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。例如 19 在区间[1, 100] 内就是一个特立独行的幸福数，其独立性为 2×4=8。
另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如 29 迭代得到 85、89、145、42、20、4、16、37、58、89、…… 可见 89 到 58 形成了死循环，所以 29 就不幸福。
本题就要求你编写程序，列出给定区间内的所有特立独行的幸福数和它的独立性。
输出格式：
按递增顺序列出给定闭区间 [A,B] 内的所有特立独行的幸福数和它的独立性。每对数字占一行，数字间以 1 个空格分隔。
如果区间内没有幸福数，则在一行中输出 SAD。
输入样例 1：
10 40
输出样例 1：
19 8 23 6 28 3 31 4 32 3
**注意：**样例中，10、13 也都是幸福数，但它们分别依附于其他数字（如 23、31 等等），所以不输出。其它数字虽然其实也依附于其它幸福数，但因为那些数字不在给定区间 [10, 40] 内，所以它们在给定区间内是特立独行的幸福数。
输入样例 2：
110 120
输出样例 2：
SAD
解答
- 判断特立独行，关于
10与13在10到40中为什么不是特立独行的数？
- 因为
10在31的迭代路径里面 13在23的迭代路径里面
- 关于如何判断特立独行在判断一个数是否是特立独行的时候，只需要看该数是否存在于该区间的平方和的原因是：特立独行的幸福数的独立性是指这个数依附于其他幸福数的个数为0。而根据题目的描述，如果一个数是幸福数，那么它一定是通过某个幸福数迭代得到的。因此，如果一个数是幸福数，那么一定存在一个幸福数，使得这个幸福数的平方和等于这个数。所以有这样一个函数
// 判断这个数在该区间是否特立独行 bool identi(int n, int left, int right){ for(int i = left; i <= right; i++){ if(n == idenNum[i]) return false; } return true; }
idenNum是一个已经初始化的数组，其内容为区间为[left, right]位置对应的平方和
这样就可以判断该数在指定区间是否是特立独行（不在该区间数的迭代路径上）
完整代码
#include <iostream> #include <vector> #include <cmath> #include <unordered_set> int idenNum[10001]; // 判断特立独行的数组 using namespace std; // 计算一个数字的各位数字的平方和 int calculateSquareSum(int n) { int sum = 0; do{ sum += pow(n % 10, 2); }while(n /= 10); return sum; } // 判断一个数字是否是素数 bool isPrime(int n) { for(int i = 2; i < sqrt(n); i++){ if(n % i == 0) return false; } return true; } // 判断一个数字是否是幸福数并且返回0或者迭代个数 int isHappy(int n){ unordered_set<int> s; // 查看是否有重复 while(s.find(n) == s.end()){ if(n == 1) return s.size(); s.insert(n); n = calculateSquareSum(n); } return 0; } // 判断这个数在该区间是否特立独行 bool identi(int n, int left, int right){ for(int i = left; i <= right; i++){ if(n == idenNum[i]) return false; } return true; } int main() { int left, right; cin >> left >> right; int flag = true; // 初始化特立独行的筛查数组 for(int i = left; i <= right; i++) idenNum[i] = calculateSquareSum(i); for(int i = left; i <= right; i++){ int sum = isHappy(i); if(sum && identi(i, left, right)){ cout<< i<<" "; if(isPrime(i)) cout<< 2 * sum<<endl; else cout<<sum<<endl; // 出现一个特立独行幸福则就不会出现SAD flag = false; } } if(flag) cout<< "SAD" <<endl; }
