题目描述给定一个数字字符串它可能表示某个数在某种进制下的形式。将该字符串按进制bbb解释为一个十进制整数NNN即N∑idibk−iN \sum_{i} d_i b^{k-i}N∑i​di​bk−i。要求找到最小的进制bbb2≤b1002 \le b 1002≤b100使得NNN是一个完全平方数。输入包含多行每行一个字符串以单独一行0结束。输入格式多行输入每行一个由数字0到9组成的字符串。输入以单独一行0结束。输出格式对于每个输入字符串输出一行一个整数表示满足条件的最小进制bbb。样例输入61 1100 509 510 1013 0输出8 3 12 16 6题目分析本题的核心是枚举进制bbb将给定字符串按该进制转换为十进制数然后判断该数是否为完全平方数。由于进制范围有限小于100100100且每个输入字符串在十进制下的值不超过10910^9109因此枚举bbb并进行转换和平方根判断是可行的。需要特别注意进制bbb必须大于字符串中出现的最大数字字符因为任何进制中的数字必须小于进制。因此可以从max_digit 1开始枚举。解题思路读入一行字符串line若为0则结束。找出字符串中最大的数字字符记为max_digit则最小可能的进制为min_base max_digit 1因为数字最大为999进制至少为101010可能。从min_base到999999枚举进制bbb将字符串按进制bbb转换为十进制数NNN使用646464位整数因为10910^9109以内。计算NNN的平方根root sqrt(N)取整。检查root * root N或(root-1)*(root-1) N或(root1)*(root1) N为避免浮点误差直接检查相邻整数。若满足则输出bbb并跳出循环。题目保证存在解且b100b 100b100。复杂度分析每个字符串长度L≤10L \le 10L≤10进制枚举最多100−min_base100 - \text{min\_base}100−min_base次每次转换O(L)O(L)O(L)总操作数不超过100×101000100 \times 10 1000100×101000非常快。空间复杂度O(L)O(L)O(L)。代码实现// Squares(III)// UVa ID: 636// Verdict: Accepted// Submission Date: 2016-08-16// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line),line!0){intmin_base2;for(inti0;iline.length();i){intdigitline[i]-0;if(digitmin_base)min_basedigit1;}for(intbmin_base;b100;b){longlongintn0;for(inti0;iline.length();i)nn*bline[i]-0;longlongintrootsqrt(n);if(root*rootn||(root-1)*(root-1)n||(root1)*(root1)n){coutb\n;break;}}}return0;}总结本题通过枚举进制并检查平方数利用进制范围小的特点简单高效地解决了问题。关键点在于确定进制下界最大数字加111以及处理平方根整数比较时的浮点误差。该解法直观易懂适用于进制枚举类问题。