UVA11549 Calculator Conundrum 题解 （STL set）

题目传送门
虽然是一个蓝题但个人认为只有橙或黄的难度，可以说是大水题了。

题目分析

通过我浅陋的数论知识很难找出它的规律。
于是考虑暴力。
很容易想到根据题意来模拟，当取到的数字呈现周期性，即与先前取过的数字出现重复时循环终止。
判重可以使用 std::set ，当 \(k\) 存在于集合中时， count() 返回 \(1\)，否则为 \(0\)。
另外由于集合中数据是已经排好序的，无需维护最大值，最后直接输出集合中的最后一个元素即可。
时间复杂度难以求出，但可以枚举 \(n\) 和 \(k\) 找到周期上界。
详细细节见代码注释。

代码

#include
using namespace std;
typedef long long ll;

int T,n;
ll k,maxnum;
set uniq;
int pow10[10] = {0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999}; //对 10 的幂打表，优化

ll rd()
{
	ll x = 0; int sgn = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * sgn;
}

int main()
{
	T = rd();
	while(T--)
	{
		uniq.clear(); //注意多组数据
		n = rd();
		k = rd();
		maxnum = pow10[n];
		uniq.insert(k); //第一次给定的 k 一定满足位数不大于 n，直接插入
		for(;;)
		{
			k *= k;
			while(k > maxnum) k /= 10; //当 k 的位数大于 n 位时，取前 n 位数字
			if(uniq.count(k) ) break; //出现重复，跳出循环
			uniq.insert(k); //否则插入集合
		}
		cout << *(--uniq.end() ) << endl; //输出集合中最后一个元素
	}
	return 0;
}

评测记录，吸氧后 \(480ms\)。