← 返回题目列表

Codeforces · 2193/E

E. 产品查询

中文机器翻译题面 查看原题

今天,Sabyrzhan 被召集到董事会,带着一个长度为 $$$n$$$ 的数组 $$$a$$$,并被分配了一项官员任务 — 回答 $$$n$$$ 问题。

在第 $$$i$$$ 题中,要求确定需要从棋盘中选择的数组中的最小元素数(允许多次使用同一个元素),使得它们的乘积恰好等于 $$$i$$$,或者报告不可能达到这样的乘积。

请注意,必须至少选择一个元素。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10 ^ 5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。

保证所有测试用例中 $$$n$$$ 的值之和不超过 $$$3 \cdot 10 ^ 5$$$。

输出

对于第 $$$i$$$ 问题,输出一个整数 — 获得等于 $$$i$$$ 的乘积所需的数组中的最小元素数量,如果不可能获得这样的乘积,则输出 $$$−1$$$。

示例

输入
复制

6
8
3 2 2 3 7 3 6 7
5
1 2 3 4 5
3
1 1 1
10
2 1 2 1 3 5 5 7 7 7
4
1 1 2 2
1
1

输出
复制

-1 1 1 2 -1 1 1 3
1 1 1 1 1
1 -1 -1
1 1 1 2 1 2 1 3 2 2
1 1 -1 2
1

注意

考虑第一个测试用例。产品可通过以下方式获得:

  • 无法获取$$$1$$$。
  • $$$2$$$可以通过选择$$$a_2$$$获得。
  • $$$3$$$可以通过选择$$$a_1$$$获得。
  • $$$4$$$可以通过选择$$$a_2$$$两次获得。
  • 无法获取$$$5$$$。
  • $$$6$$$可以通过选择$$$a_7$$$获得。
  • $$$7$$$可以通过选择$$$a_5$$$获得。
  • $$$8$$$可以通过选择$$$a_2$$$ 3次获得。