算法题解：

一、题目描述

给定 $T$ 组数据，每组输入一个整数 $x$。

对于一个正整数 $a$，定义：

• $\operatorname{len}(a)$：$a$ 的十进制位数；
• $\operatorname{sum}(a)$：$a$ 各位数字之和。

要求找到最小的正整数 $a$，满足：

$$\operatorname{len}(a)\times\operatorname{sum}(a)=x$$

如果不存在满足条件的 $a$，则输出 -1。

题目规定答案 $a$ 的位数不超过 17 位。

例如，当 $x=20$ 时，可以取 $a=19$。

19 有 2 位，数位和为：

$$1+9=10$$

因此：

$$2\times10=20$$

所以 19 是满足条件的答案。

---

二、思路分析

设答案 $a$ 有 $k$ 位，数位和为 $s$，那么题目的条件可以表示为：

$$k\times s=x$$

因此，如果确定了 $k$，那么数位和 $s$ 也就确定了：

$$s=\frac{x}{k}$$

所以可以枚举答案的位数。

1. 枚举答案的位数

因为正整数的位数越少，数值一定越小，所以从小到大枚举 $k$。

对于每个 $k$，首先判断 $x$ 是否能被 $k$ 整除：

if (x % k != 0)
    continue;

如果不能整除，则不存在 $k$ 位、满足条件的数字。

如果可以，则：

$$s=\frac{x}{k}$$

一个 $k$ 位正整数的数位和最小为 1，最大为 $9k$，因此还需要满足：

$$1\leq s\leq9k$$

如果不满足，则当前位数不可能构造出答案。

找到第一个满足条件的 $k$ 后，只需要构造这个位数下数位和为 $s$ 的最小数字即可。

2. 构造最小数字

现在已经确定：

$$\operatorname{len}(a)=k$$

以及：

$$\operatorname{sum}(a)=s$$

接下来需要构造一个最小的 $k$ 位数。

为了让数字尽可能小，应该让高位尽可能小，把较大的数字尽可能放到低位。

例如，要求构造一个三位数，数位和为 20。

可以构造：

992

也可以构造：

299

两者的数位和都是 20，但：

$$299<992$$

因此应该从最低位开始尽可能填入 9。

3. 最高位不能为 0

直接从最低位开始填 9 会遇到一个问题：最高位不能为 0，否则得到的数字就不足 $k$ 位。

因此可以先给最高位预留一个 1。

也就是先执行：

$$s\leftarrow s-1$$

这样就保证了最后最高位至少为 1。

然后从最低位开始，每一位尽可能放入 9。

如果当前剩余的数位和不足 9，就将剩余部分全部放在当前位。

最后，如果还有剩余数位和，就加到最高位之前预留的 1 上。

例如：

$$k=3,\quad s=20$$

首先为最高位预留 1：

$$s=20-1=19$$

然后从最低位开始：

个位：9，剩余 10
十位：9，剩余 1

此时已经没有其他位置可以放置，所以将剩余的 1 加到最高位：

最高位：1 + 1 = 2

最终得到：

299

其数位和为：

$$2+9+9=20$$

因此：

$$3\times20=60$$

所以 299 是 $x=60$ 时的最小答案。

4. 为什么这种构造是最小的

对于位数和固定的两个数字，如果它们在高位出现不同，那么高位更小的数字一定更小。

因此，为了使最终数字最小，应该优先保证高位尽可能小。

等价地说，就是把较大的数位尽可能放到低位。

从最低位开始不断填 9，正好实现了这一点。

---

三、算法流程

对于每组 $x$：

1. 从 len = 1 到 17 枚举答案位数。
2. 判断 x 是否能被 len 整除。
3. 计算：

$$sum=\frac{x}{len}$$

4. 判断是否满足：

$$1\leq sum\leq9\times len$$

5. 如果不满足，继续枚举下一种位数。
6. 如果满足，先给最高位预留 1。
7. 从最低位开始，每次尽可能填入 9。
8. 最后将剩余的数位和加到最高位。
9. 由于 len 是从小到大枚举的，第一个构造出的数字就是最终答案。
10. 如果 1 ~ 17 位都无法构造，则输出 -1。

---

四、代码实现

答案使用 string 保存，而不是使用 long long 保存整个数字。

因为本题的核心是逐位构造数字，使用字符串更加自然，同时也不依赖答案具体的位数限制。

#include <bits/stdc++.h>
using namespace std;

// 根据位数 len 和数位和 sum
// 构造最小的 len 位正整数
string build(int len, int sum) {
    string ans(len, '0');

    // 最高位预留 1
    sum--;

    // 从最低位开始尽可能填 9
    for (int i = len - 1; i >= 1; --i) {
        int digit = min(sum, 9);

        ans[i] = '0' + digit;
        sum -= digit;
    }

    // 剩余部分放到最高位
    ans[0] = '0' + sum + 1;

    return ans;
}

string solve(long long x) {
    // 枚举答案位数
    for (int len = 1; len <= 17; ++len) {
        // x = len * sum
        if (x % len != 0)
            continue;

        int sum = x / len;

        // len 位数的数位和范围为 [1, 9 * len]
        if (sum < 1 || sum > 9 * len)
            continue;

        // 找到最小可行位数，直接构造答案
        return build(len, sum);
    }

    return "-1";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        long long x;
        cin >> x;

        cout << solve(x) << '\n';
    }

    return 0;
}

---

五、复杂度分析

设答案最多有 $L$ 位。

枚举答案位数需要 $O(L)$，找到可行位数后构造答案需要 $O(L)$，因此总时间复杂度为：

$$O(L^2)$$

空间复杂度为：

$$O(L)$$

本题中 $L\leq17$，因此实际计算量非常小。

---

六、总结

本题的关键是将问题拆成两个部分。

首先利用：

$$\boxed{x=\operatorname{len}(a)\times\operatorname{sum}(a)}$$

枚举答案的位数，并确定对应的数位和。

然后在确定位数和数位和的情况下，利用贪心构造最小数字：

先给最高位预留 1，再从最低位开始尽可能填入 9，把较大的数字尽可能放到低位。

最终算法可以概括为：

$$\boxed{\text{枚举位数}\rightarrow\text{确定数位和}\rightarrow\text{从低位贪心构造}}$$

构造部分的核心就是：

$$\boxed{\text{最高位预留 1，剩余数位和从低位开始尽可能填 9}}$$