题目详解

给定一个奇数 $n$，需要构造 $n$ 个不同的 $n$ 位整数（无前导零），每个整数都是完全平方数，且所有数的 数字多重集 相同。

关键观察

• 如果 $x$ 是平方数，则 $100x = (10\sqrt{x})^2$ 也是平方数，且长度增加 $2$。
• 特殊的平方数形如 $(3 \cdot 10^{k+1} + 1)^2 = 9\underbrace{0\dots0}_{k}6\underbrace{0\dots0}_{k}1$
  和 $(10^{k+1} + 3)^2 = 1\underbrace{0\dots0}_{k}6\underbrace{0\dots0}_{k}9$，其中 $k \ge 0$。
• 这些数的数字多重集都包含一个 $1$、一个 $6$、一个 $9$ 和 $2k$ 个 $0$。

构造方法（递推）

基础情况：

• $n = 1$：$1$（即 $1^2$）
• $n = 3$：$169\;(13^2)$，$196\;(14^2)$，$961\;(31^2)$

递推步骤：
对任意奇数 $n \ge 5$，令 $k = \frac{n-3}{2}$（整数）。

1. 对 $n-2$ 的所有解，在每个数后面添加两个 0，得到 $n-2$ 个长度为 $n$ 的平方数。
2. 再添加两个新数：
   • $A = 9\underbrace{0\dots0}_{k}6\underbrace{0\dots0}_{k}1$
     （即 $(3 \cdot 10^{k+1} + 1)^2$）
   • $B = 1\underbrace{0\dots0}_{k}6\underbrace{0\dots0}_{k}9$
     （即 $(10^{k+1} + 3)^2$）

这样总共得到 $(n-2) + 2 = n$ 个不同的 $n$ 位平方数，且它们的数字多重集相同（都包含一个 $1$、一个 $6$、一个 $9$ 和 $2k+2$ 个 $0$）。

正确性验证

• 长度：$A$ 和 $B$ 的位数恰好为 $1 + k + 1 + k + 1 = 2k+3 = n$。
• 无前导零：最高位分别为 $9$ 和 $1$，满足条件。
• 平方性：由展开式可得：$$(3 \cdot 10^{k+1} + 1)^2 = 9 \cdot 10^{2k+2} + 6 \cdot 10^{k+1} + 1 $$对应数字序列 $9$，$k$ 个 $0$，$6$，$k$ 个 $0$，$1$。$$(10^{k+1} + 3)^2 = 10^{2k+2} + 6 \cdot 10^{k+1} + 9 $$对应数字序列 $1$，$k$ 个 $0$，$6$，$k$ 个 $0$，$9$。
• 多重集相同：所有数均由 $\{1,6,9\}$ 各一个和 $(n-3)$ 个 $0$ 组成（因为 $n$ 位，除去三个非零数字，剩下 $n-3$ 个零）。

算法实现

按上述递推预计算所有 $n \le 99$ 的解，然后对每个测试用例直接输出。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MAX_N = 99;

vector<vector<string>> precompute() {
    vector<vector<string>> sol(MAX_N + 1);
    // 基础情况
    sol[1] = {"1"};
    sol[3] = {"169", "196", "961"};
    // 递推构造 n = 5, 7, 9, ..., 99
    for (int n = 5; n <= MAX_N; n += 2) {
        int k = (n - 3) / 2;          // 中间零的个数
        string s1 = "9" + string(k, '0') + "6" + string(k, '0') + "1";
        string s2 = "1" + string(k, '0') + "6" + string(k, '0') + "9";
        // 从 n-2 的解添加 "00" 得到新解
        for (const string& x : sol[n-2]) {
            sol[n].push_back(x + "00");
        }
        sol[n].push_back(s1);
        sol[n].push_back(s2);
    }
    return sol;
}

int main() {
    auto solutions = precompute();
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (const string& s : solutions[n]) {
            cout << s << "\n";
        }
    }
    return 0;
}

复杂度

• 预处理时间 $O($$n^2$$)$，满足 $n^2$ 总和限制。
• 每个测试回答时间 $O(n)$。