蓝桥杯2014年第五届真题-拼接平方数 （C++代码）

解题思路:
        

        因为Case数据有点大，建表不太好，一个个数判断平方数大概也会超时，我们选择一个巧妙的方法获取

区间内平方数，区间值开方 获取某一段数再逐个平方存起来 就达成目的了( 注意区间起始点要向上取整 )，然

后分割判断即可。大概也不是很难。

参考代码:

#include <iostream>
#include <cmath>
using namespace std;

	/*				获取区间平方数				*/
int find_Square(int start, int end, int squart[]) {
	int total = 0;
	for (int i = start; i <= end; i++)
		squart[total++] = i * i;
	return total;
}

	/*				判断区间平方数			   */
	/*		@param last 分割数字的后面部分		*/
	/*		@param part 分割位数所用的模数		*/
	/*		@param length 区间平方数的个数	*/
void splice_Square(int squart[], int length) {
	for (int i = 0; i < length; i++) {
		int part = 10, temp = squart[i], last;

		while (temp / part > 0) {
			last = temp % part;
			temp /= part;
			
			/*		取开方丢弃小数		*/
			int sqrt_last = (int)sqrt(last);
			int sqrt_temp = (int)sqrt(temp);

			/*		0 不被当作平方数	*/
			if (last != 0 && temp != 0 && sqrt_last*sqrt_last == last &&
				sqrt_temp*sqrt_temp == temp) {
				cout << squart[i] << endl;
				break;
			}
			
			/*	part*10 进一步分割	 */
			part *= 10;
			
			/*	重置平方数	*/
			temp = squart[i];
		}
	}
}

int main() {
	int start, end, square[1000];
	cin >> start >> end;
	int length = find_Square(ceil(sqrt(start)), sqrt(end), square);

	splice_Square(square, length);
	return 0;
}