uva 11549 CALCULATOR CONUNDRUM

题目链接

刘汝佳算法竞赛经典入门训练指南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;
}