一道由数学作业延伸出的构造题

先放原题：

将正整数$1, 2, 3, \dots, 30$划分为$k$组，使得每组内任意两数之和不等于任何完全平方数。求$k$的最小值。(《培优新方法》八年级数学 §23 第3题）

嗯，对手搓暴力枚举来说数据确实大了点。抱着“反正也不可能求出正解”的心态，我尝试遍历了这些数，在第$i$遍历时，将符合要求的数依次加入第$i$组。具体来讲，如果数$g$和第$i$组里的任何数之和都不是完全平方数，则将$g$加入该组并在随后的遍历中忽略。最终一共遍历了$3$遍才将所有数分完，所以我大剌剌填了$3$上去。往后一翻——答案就是$3$。

然后某人发表暴论：“这有点像一道编程题。我在一本讲程序设计的书上看到过。”我同意。于是就有了这篇水帖。

现在问题变成了：

输入正整数$n$，将集合$\{1, 2, \dots, n\}$划分为$k$个子集$S_1, S_2, \dots, S_k$，有$\forall i, j, S_i \cap S_j = \emptyset$，且有$\forall a, b \in S_i, a + b \neq x^2 \space (x \in \mathbb{N})$。输出最小的$k$及具体划分方案（所以别想打表）。

首先我们证明上面贪心算法的正确性。令第$i$趟遍历构成集合$S_i$。为了保证$S_i$符合要求，即$\forall a, b \in S_i, a + b \neq x^2 \space(x \in \mathbb{N})$，对于扫描到的任意两个冲突的数，它们一定不能处于同一集合中，也即至少需要一个新集合来处理冲突的数，不会使最终结果变差。而我们将任意两个不冲突的数都尽可能放入同一集合中（应收尽收），综上这能够保证$k$最小。

我们可以预处理出不超过$(2n-1)$的完全平方数。由于我们采用顺序遍历，易知扫描到数$g$时，只需检查完全平方数$x \in [g, 2g]$，查询数$(x-g)$是否在$S_i$中即可。用简化版的并查集实现集合的查询和合并。

哦，你说时间复杂度？我没能准确地算出来。根据之前尝试的结果，数据在$2\times 10^5$以内时，时间都还可以接受。但若假设每个数平均会在遍历$t$遍之后被划分到一个集合中；易知每次检查数$g$，都将扫描约$\sqrt{2g}-\sqrt{g} = (\sqrt{2}-1)\sqrt{g}$个数，共花费$q = (\sqrt{2}-1)\sum\limits_{g=1}^{n}{\sqrt{g}}$的时间；二分查找花费$\log$级别的时间，故最终大约花费$\mathrm{O}(t(n\log\sqrt{n}+q))$的时间。

这应该不是最高效的算法。（是，我明白，这的确挺暴力的，但我也想不出其他办法。）欢迎从数轮角度分析并提出更快的解法。

我也想过二分$k$的值（很明显答案具有单调性），但不妙的是，至今我仍未想出check ()函数怎么写。如何高效地判定在分$ans$组时能否满足要求呢？

或者，有无可能……直接推导出某一数学结论呢？

总之，上述解法的代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

const int N = 1024000;
int n, ans, x, cnt, q;
int fa[N], nums[N];
bool solved[N];

void solve (int g) {
	int p = upper_bound (nums + 1, nums + 1 + q, g) - nums; // 最小的大于g的完全平方数 
	for (int i = p; i <= q && nums[i] < g<<1; ++i)
		if (fa[nums[i] - g] == fa[x]) // 分组冲突 
			return;
	fa[g] = fa[x]; // 合并 
	solved[g] = 1; ++cnt;
}

int main () {
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i)
		fa[i] = i; // 初始化并查集 
	for (int i = 1; i * i <= n<<1; ++i)
		nums[++q] = i * i; // 预处理完全平方数 
	while (cnt < n) {
		++ans, x = 1; // 新一轮遍历 
		while (solved[x]) ++x;
		for (int i = x; i <= n; ++i)
			if (!solved[i])
				solve (i);
	} 
	
	printf ("%d", ans);
	// 我懒，所以就不去重并输出具体方案了（雾 

	return 0;
}