蓝桥杯2014年第五届真题-拼接平方数

题目

题目链接

题解

实现题。

题目大意： 将一个区间内的数拆成两个数后，若原数、拆得的第一个数和拆得的第一个数均为平方数则输出。

直接遍历区间内所有的数可能会超时，因此我们直接取区间内的平方数，只遍历区间内的平方数，时间复杂度会降很多。 对于每个遍历到的数，我们将其拆分成两个数，其实就是枚举分割线在哪里，判断得到的两个数是不是平方数，若都是平方数且不为0，则说明遍历到的数是一个可以拆分成两个平方数的平方数，输出。

代码

#include
using namespace std;

int aa[110];

bool check(int x) {
	int t = sqrt(x);
	if(x == 0 || t*t != x) return false;
	return true;
}

int main()
{
	int a, b, l, r;
	cin>>a>>b;
	r = sqrt(b);
	l = sqrt(a);
	if(l*l != a) l++;

	for(int i = l;i