刘汝佳算法竞赛经典入门训练指南p42
代码1：
#include <set> #include <iostream> #include <sstream> using namespace std; int next(int n, int k) { stringstream ss; ss <<(long long)k*k; string s = ss.str(); if (s.length() > n) s = s.substr(0, n); int ans = 0; stringstream ss2(s); ss2 >> ans; return ans; } int main() { int t; int n, k; cin>>t; while (t--) { cin>>n>>k; set<int> s; int ans = k; while (!s.count(k)) { s.insert(k); if (k > ans) ans = k; k = next(n, k); } cout << ans << endl; } return 0; }
代码2：
#include <set> #include <iostream> #include <sstream> using namespace std; int next(int n, int k) { int buf[10]; if (!k) return 0; long long k2 = (long long)k*k; int l = 0; while (k2 > 0) { buf[l++] = k2%10; k2 /= 10; } if (n > l) n = l; int ans = 0; for (int i = 0; i < n; i++) ans = ans*10 + buf[--l]; return ans; } int main() { int t; int n, k; cin>>t; while (t--) { cin>>n>>k; set<int> s; int ans = k; while (!s.count(k)) { s.insert(k); if (k > ans) ans = k; k = next(n, k); } cout << ans << endl; } return 0; }
代码3（Floyd判圈法）：
#include <set> #include <iostream> #include <sstream> using namespace std; int buf[10]; int next(int n, int k) { if (!k) return 0; long long k2 = (long long)k*k; int l = 0; while (k2 > 0) { buf[l++] = k2%10; k2 /= 10; } if (n > l) n = l; int ans = 0; for (int i = 0; i < n; i++) ans = ans*10 + buf[--l]; return ans; } int main() { int t; int n, k; cin>>t; while (t--) { cin>>n>>k; int ans = k; int k1 = k, k2 = k; do { k1 = next(n, k1); k2 = next(n, k2); if (k2 < ans) ans = k2; k2 = next(n, k2); if (k2 < ans) ans = k2; }while (k1 != k2); cout << ans << endl; } return 0; }
