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

题目

题目链接

题解

实现题。

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

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

代码

#include<bits/stdc++.h>
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 <= r;i ++) {
		int x = i*i, cnt = 0, flag = 0;
		while(x) ++ cnt, x /= 10;
		x = i*i;
		for(int j = 1, num = 10;j < cnt;j ++, num *= 10) 
		if(check(x%num) && check(x/num)) 
		{flag = 1; break;}
		if(flag) cout << x << endl;
	}
	return 0;
}