题目链接
刘汝佳算法竞赛经典入门训练指南p42
代码1：
代码语言：javascript复制#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：
代码语言：javascript复制#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; 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判圈法）：
代码语言：javascript复制#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; 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;
}
