P8447 (Official)

035966_L3 · 2022-05-25 12:34:50 · 题解

说句闲话：

• 出题人这题做了半年。
• 当 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。

  根据这个定理，总有四个非负整数 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 分）：按照与加强前的原题中 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：

#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;
}