「DROI」Round 1 下坠

Luogu
IDLGP8982
Time500ms
Memory128MB
DifficultyP5
贪心洛谷原创O2优化
$f$ 是定义在 $\mathbb{N^+}$ 上的函数。 我们令 $a_i$ 表示 $x$ 从低到高第 $i$ 位,那么 $f(x)= \prod_{i=1}^{len} (a_i+1)$($len$ 表示 $x$ 的位数)。 如果对于一个数 $x$,存在 $y$ 使得 $f(y)=x$,那我们称 $x$ 是下坠数。 现在有 $Q$ 次询问,每次询问会给出一个正整数 $k$。 令 $x$ 表示所有下坠数中第 $k$ 小的下坠数,那么请你找到一个**最小的** $y$,使得 $f(y)=x$。若不存在一个 $y \in [1,10^{18}]$ 满足条件,则输出 $-1$。 ## Input 第一行输入一个整数 $Q$,表示询问次数。 接下输入一行 $Q$ 个数,第 $i$ 个数表示第 $i$ 次询问的 $k$。 ## Output 输出一行 $Q$ 个数,第 $i$ 个数表示第 $i$ 次询问你找到的答案。 [samples] ## Background 下坠是有终点的吗? ## Note #### 样例解释 #1 注意到 $f$ 的定义域是 $\mathbb{N^+}$,所以 $1$ 不是下坠数。则前三个下坠数分别为 $2,3,4$,对应的 $y$ 值则为 $1,2,3$。 ------------ #### 样例解释 #2 第 $9$ 和 $14$ 个下坠数分别为 $10$ 和 $18$,其对应的 $y$ 值则为 $9$ 和 $18$。可以证明,第 $46666666$ 个下坠数对应的 $y > 10^{18}$。 ------------ #### 数据范围 对于 $100\%$ 的数据满足:$Q \leq 10^5$,$k \leq 5 \times 10^7$。 其中对于 $10\%$ 的数据满足:$k \leq 100$。 对于 $30\%$ 的数据满足:$k \leq 5 \times 10^3$。 对于另外 $20\%$ 的数据满足:对于所有被询问到的下坠数 $x$,都有 $\vert x-y \vert \leq 100$ 或者 $y > 10^{18}$。 **请注意不同寻常的时间限制。**
Samples
Input #1
3
1 2 3
Output #1
1 2 3
Input #2
3
9 14 46666666
Output #2
9 18 -1
API Response (JSON)
{
  "problem": {
    "name": "「DROI」Round 1 下坠",
    "description": {
      "content": "$f$ 是定义在 $\\mathbb{N^+}$ 上的函数。 我们令 $a_i$ 表示 $x$ 从低到高第 $i$ 位,那么 $f(x)= \\prod_{i=1}^{len} (a_i+1)$($len$ 表示 $x$ 的位数)。 如果对于一个数 $x$,存在 $y$ 使得 $f(y)=x$,那我们称 $x$ 是下坠数。 现在有 $Q$ 次询问,每次询问会给出一个正整数 $k$。 令 $x$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8982"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$f$ 是定义在 $\\mathbb{N^+}$ 上的函数。\n\n我们令 $a_i$ 表示 $x$ 从低到高第 $i$ 位,那么 $f(x)= \\prod_{i=1}^{len} (a_i+1)$($len$ 表示 $x$ 的位数)。\n\n如果对于一个数 $x$,存在 $y$ 使得 $f(y)=x$,那我们称 $x$ 是下坠数。\n\n现在有 $Q$ 次询问,每次询问会给出一个正整数 $k$。\n\n令 $x$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments