解题思路

设编号 $z$ 有 $L$ 位、各位之和为 $s(z)$ ，题面要求 $L\cdot s(z)=w$ ，并在 $[1,10^{16}]$ 里找最小的 $z$ 。

$L$ 必须是 $w$ 的约数，且 $s=w/L$ 满足 $1\le s\le 9L$ （每位最多 $9$ ）。 $L$ 越大， $z$ 的位数越多，数值一定更大，所以从 $L=1$ 枚举到 $L=17$ 即可， $17$ 是上界 $10^{16}$ 的位数。
对固定的 $L$ 和 $s$ ，要拼出最小的 $L$ 位数。最高位至少是 $1$ ，又至少要留给后面 $L-1$ 位每人最多 $9$ 之后仍能凑满 $s$ ，因此最高位取 $\max(1,s-9(L-1))$ ；剩下的和尽量堆到最右边。
$L=17$ 时，闭区间里只有 $10000000000000000$ 这一个数，它的数位和是 $1$ ，因此仅当 $w=17$ 时成立。
某个 $L$ 构造出的数若超过上界就丢掉；所有 $L$ 都不行则输出 $-1$ 。常见假解：只看一位数、把余数堆到左边、漏掉 $17$ 位的上界点、把质数一律判成 $-1$ （例如 $w=11$ 可以是 $11$ 位且和为 $1$ ）。

题目内容

出厂时要给设备打一个十进制编号 $z$ 。把 $z$ 写成十进制以后，把位数记成 $L$ ，把各位数字加起来记成 $s(z)$ 。

现在给出校验额度 $w$ ，要求 $L$ 与 $s(z)$ 的乘积恰好等于 $w$ 。请在闭区间 $[1,10000000000000000]$ 内挑出数值尽量小的合法编号；若一个都挑不到，就输出 $-1$ 。

位数怎么数：例如 $7$ 占 $1$ 位， $105$ 占 $3$ 位。各位怎么加：例如 $105$ 是 $1+0+5=6$ 。

第一行一个整数 $q$ ，表示询问次数。 $(1\le q\le 50000)$

第二行 $q$ 个整数 $w$ ，即每组询问的校验额度。 $(1\le w\le 2.5\times 10^{3})$

一行输出 $q$ 个整数，相邻两项用空格隔开：依次给出每组询问的最小合法编号；不存在时该位置为 $-1$ 。

输入

5
1 10 11 27 16

输出

1 14 10000000000 108 17

说明

输入

3
8 29 17

输出

8 -1 10000000000000000

说明

选择提交后点击「开始AI分析」