UVA-11549 Ca'lculator Conundrum Floyd判圈法 规律

UVA-11549 Ca'lculator Conundrum Floyd判圈法 规律

题意

给定一个老式计算器，只能显示(n)位数字。

现输入一个整数(k)，不断对这个(K)做平方运算，问题在于若计算器出现溢出，只会保留前(n)位数字。

现给出(n,k)问可能出现的最大数字是多少。

[1leq n leq 9,0leq k leq 10^9 ]

分析

显然计算机显示的数字会出现循环，否则也不会问你最大的数字是多少了。

那么我们只能猜测这个循环次数非常有限是可以遍历出来的。

最直接的想法是开一个(map)来记录这个数字。

但是可能导致空间复杂度过高，所以根据紫书我们不妨想出一个更加高效的方法：

Floyd判圈法，好像有点像快慢指针？

想象一个两个小孩在操场跑步，一个一次走一步，另一个一次走两步，那么快的小孩总是在慢的小孩前面，若存在环，我们还会发现当他们相遇的时候必然已经遍历了所有情况。

代码

int buf[105];

int next(int n, int k) {
    if (!k) return 0;
    ll k2 = (ll)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;
}


void solve() {
    int n = readint();
    ll k = readll();
    ll res = k;
    ll k1 = k, k2 = k;
    do {
        k1 = next(n, k1);
        k2 = next(n, k2); if (k2 > res) res = k2;
        k2 = next(n, k2); if (k2 > res) res = k2;
    } while (k1 != k2);
    Put(res);
    puts("");
}

int main() {
    int T = readint();
    while (T--)
        solve();
}