题目描述
对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到就称该数为幸福数。1是一个幸福数。此外，例如19经过1次迭代得到82次迭代后得到63次迭代后得到100，最后得到则19就是幸福数。显然，在一个幸福数迭代到1的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如86100的幸福是依附于19的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。例如19在区间[1,100]内就是一个特立独行的幸福数，其独立性为2×4=
另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如29迭代得到8814420、1358……可见89到58形成了死循环，所以29就不幸福。
本题就要求你编写程序，列出给定区间内的所有特立独行的幸福数和它的独立性。
输入格式
输入在第一行给出闭区间的两个端点：1 输出格式 按递增顺序列出给定闭区间[A,B]内的所有特立独行的幸福数和它的独立性。每对数字占一行，数字间以1个空格分隔。 如果区间内没有幸福数，则在一行中输出SAD。 输入样例1 输出样例1 注意：样例中，13也都是幸福数，但它们分别依附于其他数字，所以不输出。其它数字虽然其实也依附于其它幸福数，但因为那些数字不在给定区间[10,40]内，所以它们在给定区间内是特立独行的幸福数。 输入样例2 输出样例2 思路： 见代码 文章为作者独立观点，不代表股票配资公司观点
10 40
19 8
23 6
28 3
31 4
32 3
110 120
SAD
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int l, r;
int cnt[N], val[N]; // cnt:某个数出现次数 val:幸福数的独立性
bool st[N]; // 判断在一次循环中这个数是否出现过
bool check(int x) { // 判素数
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++)
if (x % i == 0)
return false;
return true;
}
int turn(int x) { // 算幸福数
int res = 0;
while (x) {
res += (x % 10) * (x % 10);
x /= 10;
}
return res;
}
int main() {
cin >> l >> r;
for (int i = l; i <= r; i ++) {
int a = i, num = 0;
memset(st, 0, sizeof st);
while (a != 1 && !st[a]) {
num ++;
cnt[a] ++;
st[a] = true;
a = turn(a);
}
if (!st[a]) {
if (check(i)) val[i] = num * 2;
else val[i] = num;
}
}
int flag = 0;
for (int i = l; i <= r; i ++) {
if (val[i] && cnt[i] == 1) { // 只有当幸福数的独立性不为0且幸福数只出现1次
flag = 1;
cout << i << " " << val[i] << endl;
}
}
if (!flag) cout << "SAD";
return 0;
}
相关文章
股民评论