自动搬运

查看原文

来自洛谷，原作者为

	幻想繁星 你我终于做了永远的哑巴,再给不出半个回答|已关闭私信接收

搬运于2025-08-24 22:40:43，当前版本为作者最后更新于2022-10-25 08:41:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（upd：2023.9.9 增添常数更小的取模分割法）

题目大意

找出一段区间的“拼接平方数”，“拼接平方数”指一个数是平方数，而且它能拆成两部分，那两个部分也是平方数，但是不能包括 $0$。

思路

由于数据范围较小，可以预处理一下所有的平方数，再枚举区间内的每一个平方数的所有分割方式，判断是否能由两个平方数组成。

时间复杂度为：$O(r)$。

实现过程

一、判断是否为平方数，为预处理平方数及“拼接平方数”做准备。

因为平方数的平方根为整数，所以将一个平方数的平方根转化为整数并不会导致精度丢失，而非平方数的平方根转化为整数则会丢失小数部分的精度。

时间复杂度：$O(1)$。

可以写出如下代码：

bool pfs(int x) { //判断平方数函数
	return (int)sqrt(x) == sqrt(x);
}

二、预处理出范围内的所有平方数。

直接从 $1$ 开始 for 循环到 $r$，判断每一个数是否为平方数，如果是就将其标记下来。

时间复杂度：$O(r)$。

代码如下：

bool f[1000005];
for (int i = 1; i <= r; i++) {//预处理1到r之间的所有平方数
	if (pfs(i))
		f[i] = 1;
}

三、判断所有的“拼接平方数”。

从 $l$ 枚举到 $r$，判断区间内每一个数是否为“拼接平方数”，如果是将其输出。

判断方法：先判断是否为平方数，如果是枚举每一种分割方式，判断是否为两个平方数组成，如果是就是“拼接平方数”。

利用 STL 的字符串与数字转化函数或模运算和除法的性质，可以轻松完分割操作。

时间复杂度：$O(r-l)$。

代码如下：

字符串：

	for (int i = l; i <= r; i++)//判断l到r的所有“拼接平方数”并输出
		if (f[i]) {
			s = to_string(i);
			int sl = s.size();
			for (int j = 1; j < sl; j++) {
				int x = stoi(s.substr(0, j));
				int y = stoi(s.substr(j));
				if (f[x] && f[y]) {
					printf("%d\n", i);
					break;
				}
			}
		}

模运算和除法（常数更小）：

	for (int i = l; i <= r; i++)//判断l到r的所有“拼接平方数”并输出
		if (f[i]) {
			int k = 10;
			for (int j = 1; j <= 5; j++) {
				int x = i % k;
				int y = i / k;
				k *= 10;
				if (f[x] && f[y]) {
					printf("%d\n", i);
					break;
				}
			}
		}

至此，此题已经基本完成。将各部分代码整理一下，就可以得到完整的 AC 代码。

AC 代码如下：

字符串分割法：

#include<bits/stdc++.h>
using namespace std;
bool f[1000005];
int l, r;
string s;
bool pfs(int x) {
	return (int)sqrt(x) == sqrt(x);
}
int main() {
	cin >> l >> r;
	for (int i = 1; i <= r; i++) {
		if (pfs(i))
			f[i] = 1;
	}
	for (int i = l; i <= r; i++)
		if (f[i]) {
			s = to_string(i);
			int sl = s.size();
			for (int j = 1; j < sl; j++) {
				int x = stoi(s.substr(0, j));
				int y = stoi(s.substr(j));
				if (f[x] && f[y]) {
					printf("%d\n", i);
					break;
				}
			}
		}
	return 0;
}

取模分割法：

#include<bits/stdc++.h>
using namespace std;
bool f[1000005];
int l, r;
string s;
bool pfs(int x) {
	return (int)sqrt(x) == sqrt(x);
}
int main() {
	cin >> l >> r;
	for (int i = 1; i <= r; i++) {
		if (pfs(i))
			f[i] = 1;
	}
	for (int i = l; i <= r; i++)
		if (f[i]) {
			int k = 10;
			for (int j = 1; j <= 5; j++) {
				int x = i % k;
				int y = i / k;
				k *= 10;
				if (f[x] && f[y]) {
					printf("%d\n", i);
					break;
				}
			}
		}
	return 0;
}

如有错误，请各位多多指教。
另附打表代码