说句闲话： 出题人这题做了半年。

Part 0

显然，无解是不可能的，因为 $n$ 个 $1^2$ 的和就是 $n$，而 $m \ge 1$，因此这一定是合法的方案。

Part 1

设答案为 $k$，求证：$p \le k \le p+4$，其中 $p=\lfloor\dfrac{n}{m^2}\rfloor$。

证明：

• 先证明 $k \ge p$：

  若 $k<p$，则 $k \cdot m^2 < p \cdot m^2$。

  显然 $p \le \dfrac{n}{m^2}$，因此 $p \cdot m^2 \le n$。

  于是，$k \cdot m^2 < p \cdot m^2 \le n$，即 $k \cdot m^2 < n$。

  由于每个完全平方数都不大于 $m^2$，因此 $k$ 个完全平方数的和最大只能是 $k \cdot m^2$。

  然而，$k \cdot m^2 < n$，因此，$k$ 个完全平方数的和绝不可能等于 $n$，矛盾。

  综上，$k<p$ 的假设不成立，因此 $k \ge p$，得证。

• 再证明 $k \le p+4$：

  设 $n=p \cdot m^2 +q$。

  显然 $p \le \dfrac{n}{m^2}<p+1$，因此 $p \cdot m^2 \le n<(p+1) \cdot m^2$，于是 $0 \le q <m^2$。

  根据这个定理，总有四个非负整数 $e_1,e_2,e_3,e_4$，使得 $q=(e_1)^2+(e_2)^2+(e_3)^2+(e_4)^2$。

  由于 $q <m^2$，而 $(e_1)^2,(e_2)^2,(e_3)^2,(e_4)^2$ 均非负，因此 $(e_1)^2,(e_2)^2,(e_3)^2,(e_4)^2$ 均不大于 $m^2$，满足「不大于 $m^2$」的要求。

  将 $q$ 代入，得 $n=p \cdot m^2 +(e_1)^2+(e_2)^2+(e_3)^2+(e_4)^2$。

  此时，等式右边共 $(p+4)$ 个完全平方数，故 $k \le p+4$（为 $0$ 的项可以删去，因此可能少于 $(p+4)$ 个），得证。

综上所述，$p \le k \le p+4$，原命题得证。

显然，由于 $p \le k \le p+4$，$k$ 的取值只有 $5$ 种（$p$，$p+1$，$p+2$，$p+3$，$p+4$）。因此，考虑暴力枚举 $k$ 的值，每次判断是否可行（若 $k \cdot m^2 < n$ 则直接跳过，保证 $k \cdot m^2 \ge n$）。

Part 2

先来考虑一种错误的解法（$40\ \text{pts}$）：按照与加强前的原题中 $O(n\sqrt{n})$ 解法类似的思路，使用完全背包求解，时间复杂度 $O(nm^2+Q)$，超时。

显然，使得上述算法超时的主要原因是状态太多（对应 $O(nm^2+Q)$ 中的 $n$）。要想优化此算法，必须减少状态数。

由于正向求解遇到了困难，考虑反向求解：每次枚举 $k$ 的值时，先假设所有的完全平方数都是 $m^2$，再把一部分 $m^2$ 修改为其它小于 $m^2$ 的完全平方数，使总和减小（倒扣），反向求解。

于是，完全背包的定义发生了转变。

Part 3

定义 $w_{i,j}$ 为：当 $m=i$ 时，恰好倒扣 $j$ 至少需要修改的 $m^2$ 的个数，若无法恰好倒扣 $j$ 则其值为 $+\infty$。（$1 \le i \le 100,j \ge 0$）

初始状态：

• $w_{i,0}=0,w_{i,j}=+\infty.$
• $j \neq 0.$
• （解释：前者无需倒扣，后者假定无法恰好倒扣，等待更新。）

状态转移方程（顺序：按 $j$ 升序）：

• $w_{i,j} = \min(w_{i,j},w_{i,j-(i^2-x^2)}+1).$
• 其中 $x=1,2,\ldots,i-1$，保证 $j-(i^2-x^2) \ge 0.$
• （解释：修改 $1$ 个 $i^2$（改为 $x^2$），倒扣 $i^2-x^2$。）

由于需要从 $k \cdot m^2$ 倒扣至 $n$，共倒扣了 $k \cdot m^2 - n$，因此 $w_{m,k \cdot m^2 - n}$ 即为所需的答案。

注意：若 $w_{m,k \cdot m^2 - n} > k$，则表明没有足够的 $m^2$ 用于倒扣时的修改（或根本不可能恰好倒扣，此时 $w_{m,k \cdot m^2 -n} = +\infty$），该 $k$ 的值必须舍去。

Part 4

求证：倒扣的总量（$k \cdot m^2 - n$，即当 $i=m$ 时下标 $j$ 的上界）不大于 $4 \cdot m^2-1$。

证明：

前面已经证明 $p \cdot m^2 \le n$。

• 当 $p \cdot m^2 < n$ 时：

  此时有 $p \cdot m^2 \le n-1$，因此 $p \cdot m^2 +4 \cdot m^2 \le n+4 \cdot m^2-1$，即 $(p+4) \cdot m^2 \le n+4 \cdot m^2-1$。

  又因为前面已经证明 $k \le p+4$，因此 $k \cdot m^2 \le (p+4) \cdot m^2$。

  于是 $k \cdot m^2 \le (p+4) \cdot m^2 \le n+4 \cdot m^2-1$，即 $k \cdot m^2 \le n+4 \cdot m^2-1$。

  由此可得 $k \cdot m^2-n \le 4 \cdot m^2-1$。

• 当 $p \cdot m^2 = n$ 时：

  显然此时 $n = p \cdot m^2$。该等式右边共 $p$ 个完全平方数，故 $k =p$（前面已经证明 $k \ge p$）。

  将上面两个等式代入计算，得 $k \cdot m^2 - n =0$。显然 $4 \cdot m^2-1>0$。

综上所述，$k \cdot m^2 \le n+4 \cdot m^2-1$，原命题得证。

若 $w_{i,j} \neq +\infty$，求证：$w_{i,j} \le 26$。

证明：

根据上文，模拟可得，过程略去。原命题得证。

Part 5

最终，时间复杂度 $O(m^4+Q)$，空间复杂度 $O(m^3)$，可以通过此题。

Part 6

std：

#include <bits/stdc++.h>
using namespace std;
const int M = 100 + 5;
vector <char> w[M];
int main() {
    for (int i = 1; i <= 100; i ++) {
        w[i].resize(4 * i * i + 5);
        w[i][0] = 0;
        for (int j = 1; j <= 4 * i * i - 1; j ++) {
            w[i][j] = 27;
            for (int x = i - 1; x >= 1; x --)
                if (j - (i * i - x * x) >= 0) w[i][j] = min(w[i][j], (char) (w[i][j - (i * i - x * x)] + 1));
        }
    }
    int Q;
    scanf("%d", &Q);
    while (Q --) {
        long long n;
        int m;
        scanf("%lld %d", &n, &m);
        long long k = n / (m * m);
        while (k * m * m < n || w[m][k * m * m - n] == 27 || w[m][k * m * m - n] > k) k ++;
        printf("%lld\n", k);
    }
    return 0;
}