P9913-SOL.

· · 题解

这是一个比较经典的问题，结论大家都知道了，蒟蒻想从头分析一遍。

看到这个题目很多人就会直接想：将正方形分割成正方形，那数量不就是完全平方数吗？没错，所以完全平方数当然可以。

但是递交上去之后很多人就爆零了，原因是正方形大小不一定相同，那我们就可以将一个正方形分成几个小正方形，或者将几个小正方形合并成一个。

我们可以首先将一个小正方形分割成 4 个。照这样，1 个小正方形就可以分割成 4 个，4 个小正方形中的一个再分割就可以分割成 7 个……以此类推，所有满足 n 为自然数的 3n + 1 都满足题目要求。

我们继续向下尝试，然后就是 9 个。照这样，1 个小正方形就可以分割成 9 个，9 个小正方形中的一个再分割就可以分割成 17 个……以此类推，所有满足 n 为自然数的 8n + 1 都满足题目要求。

如果是 16 个呢？照这样，1 个小正方形就可以分割成 16 个，16 个小正方形中的一个再分割就可以分割成 31 个……以此类推，所有满足 n 为自然数的 15n + 1 都满足题目要求，但很显然这些数构成的集合包含于 3n + 1，所以我们不单独列出来算。

再往后，25 个，36 个……我们会发现最后其实只有 3n + 1 和 8n + 1 两种数满足题目要求，于是分割这一块就结束了。

上面已经提到了合并，我们现在就来尝试一下。

我们要合并，那么我们最好选择一个初始的方阵，不能太小，但也不要太大，比如我们可以从 16 个小正方形开始合并。

我们可以首先将 4 个小正方形合并成一个。照这样，16 个小正方形就可以合并成 13 个，10 个，7 个或 4 个。

我们也可以选择 9 个。照这样，16 个小正方形就可以合并成 8 个。

选择再多的小正方形合并与分割同理，没有必要列举。

我们已经推算出来，7 个，8 个或 9 个小正方形都是满足条件的，于是之后的正方形数量至少都可以通过分裂来得到（每次分裂加三个小正方形）。那么 7 个以下的呢？

显而易见，6 个小正方形可以是 9 个小正方形进行一次合并得到，4 个小正方形可以通过分裂得到，而 1 个就更不用说了，而 2 个，3 个或 5 个小正方形却无论如何得不出来。因为 6 个小正方形不能再合并，8 个小正方形也不能。

（最后我们发现，其实完全平方数完全可以不单拎出来，直接作为分裂的一种。）

所以最后只需要判断一下数字是不是 2，3，5 以外的数即可。