题意: 一个老式计算器,只能显示n(1 <= n <= 9)位, 现给定k(0 <= k <= 1E+n),求其平方,若溢出保留前n位,问一直计算下去能得到的最大值;
分析 :
题中隐约告诉我们有循环,显然如果出现两个相同的数,这两个之间便是一个循环
而一个计算器能显示的数是有限的,所以必然会出现相同的数
#include <iostream> #include <cstdio> using namespace std; int next(int n, int k) { if(!k) return 0; long long sum = (long long)k * (long long)k; int len = 0; int a[100]; while(sum > 0) { a[len++] = sum % 10; sum /= 10; } if(n > len) n = len; int ans = 0; for(int i = 0; i < n; i++) ans = ans * 10 + a[--len]; return ans; } int main() { int T; scanf("%d", &T); while(T--) { int n, k; scanf("%d%d", &n, &k); int k1 = k, k2 = k; int ans = k; do { k1 = next(n, k1); ans = max(ans, k1); k2 = next(n, k2); ans = max(ans, k2); k2 = next(n, k2); ans = max(ans, k2); } while(k1 != k2); printf("%d\n", ans); } return 0; } 这里用到的是Floyd判圈算法
k1每次走一步,k2每次走两步,若有环,走的快的一定会追上走的慢的
首先从上面分析知道,最小环上不可能有相同点,
在环上跑时,不管k1,k2,位置如何,k2总是相对于k1以一步每次的速度追赶k1,所以k2一定会追上k1;
