#include<iostream> #include<string> #include<set> #define maxn 10001 usingnamespacestd; int fa[maxn]; // 存的是他 的平方和 intpfh(int n); pair<int, int> findRoot(int v); //返回的pair, first:如果有循环 返回-1 其余的返回他的根 second:返回找到根的次数 boolisPrime(int x); boolisLeaf(int A, int B, int v); intmain() { int A, B; cin >> A >> B; for (int i = 1; i < maxn; ++i) fa[i] = i; for (int i = 1; i < maxn; ++i) fa[i] = pfh(i); int cnt = 0; for (int i = A; i <= B; ++i) { pair<int, int> res; res = findRoot(i); if (res.first == 1 && isLeaf(A, B, i)) { cnt++; if (isPrime(i)) res.second *= 2; cout << i << " " << res.second << "\n"; } } if (!cnt) cout << "SAD"; }
boolisLeaf(int A, int B, int v) { for (int i = A; i <= B; ++i) if (fa[i] == v) returnfalse; returntrue; } boolisPrime(int x) { for (int i = 2; i * i <= x; ++i) if (x % i == 0) returnfalse; returntrue; } pair<int, int> findRoot(int v) { set<int> s; int cnt = 0; while (fa[v] != v) { auto res = s.insert(v); if (res.second == false) //有重复 return make_pair(-1, 0); v = fa[v]; cnt++; } return make_pair(v, cnt); } intpfh(int n) { string num = to_string(n); int sum = 0; for (auto x : num) sum += (x - '0') * (x - '0'); return sum; }