P8447 (Official) - 洛谷保存站

**说句闲话：**

- 出题人这题做了半年。
- 当 $m \le 500$ 时，贪心上界是 $13853793$（$n=13853793=57 \times 493^2$，$m=494$）。

# 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$。

根据[这个定理](https://baike.baidu.com/item/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86/4507832)，总有四个非负整数 $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$ 分）：按照与[加强前的原题](https://leetcode-cn.com/problems/perfect-squares/)中 $O(n\sqrt{n})$ 解法类似的思路，使用**完全背包**求解，时间复杂度 $O(nm+Q)$，超时。

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

我们先来看一个例子：$n=50025/m=10$。显然，$50025=500 \times 10^2+5^2$，答案是 $501$。

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

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

# Part 3

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

初始状态：

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

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

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

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

**注意：若 $w_{k \cdot m^2 - n} > k$，则表明没有足够的 $m^2$ 用于倒扣时的修改（或根本不可能恰好倒扣，此时 $w_{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_{j} \neq +\infty$，求证：$w_{j} \le 57$。

**证明：**

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

# Part 5

最终，（每组数据）时间复杂度 $O(m^3+Q)$，空间复杂度 $O(m^2)$，可以通过此题。

# Part 6

std：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int M = 500 + 12;
const int K = 4 * M * M + 12;
const int W = 58;
char dp[K];
signed main()
{
   	int T;
   	scanf("%d", &T);
   	while (T--)
   	{
   		int m, Q;
   		scanf("%d %d", &m, &Q);
   		memset(dp, 0x7e, sizeof dp);
   		dp[0] = 0;
   		for (int u = 0; u <= 4 * m * m; u++)
   			for (int i = m - 1; i >= 1; i--)
   			{
   				int x = m * m - i * i;
   				if (u + x > 4 * m * m) break;
   				if (dp[u + x] > dp[u] + 1)  dp[u + x] = dp[u] + 1;
			}
		while (Q--)
		{
			long long n;
			scanf("%lld", &n);
			long long k = n / (m * m);
        	while (k * m * m < n || dp[k * m * m - n] >= W || dp[k * m * m - n] > k) k++;
        	printf("%lld\n", k);
		}
	}
    return 0;
}
```

正在渲染内容...