例题19 计算器谜题(Uva 11549) (Floyd 判圈算法)

有一个计算器只能显示 n n n位数字,输入一个整数k,然后把它反复平方直到溢出为止,然后把溢出数字最高位n作为下一次的k如此反复 思路:显然存在循环节.为什么.假设第一次溢出的数字是k1,反复平方后得到k2.如果不存在循环节, k 1 ! = k 2 k1!=k2 k1!=k2.假设进行了11次上述过程,得到了11个不同的数字,而由于最高位的数字是0~9,抽屉原理,至少有一个数字出现了两次,那么它就是循环节了. 怎么判断循环节比较快一点呢.书上提供了两种思路,开set,或者Floyd判圈. 我采用的是第二种思路.判圈就是类似于链表的快慢指针,一个走两步一个走一步,走两步的一定能追上走一步的,如果存在一个循环节.

/*
*/
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5+2;
const int INF = 1e9+7;
typedef pair pii;
int cnt[15];
ll get(ll n,ll k){
	if(k==0) return k;
	memset(cnt,0,sizeof(cnt));
	ll pow = k*k;
	int len = 0;
	while(pow){
		cnt[len++] = pow%10;
		pow/=10;
	}
	//注意位数少于n位的情况. 
	if(lenT;
	while(T--){
		ll n,k;
		cin>>n>>k;
		ll ans = k;
		ll k1 = k,k2=k;
		do{
			k1 = get(n,k1);
			ans = max(ans,k1);
			k2 = get(n,k2);ans=max(ans,k2);
			k2 = get(n,k2);ans = max(ans,k2);
		} while(k1!=k2);
		cout