英文原题

E. Product Queries

time limit per test: 3 seconds
memory limit per test: 256
megabytes input: standard
input output: standard output

Today, $Sabyrzhan$ was called to the board with an array a of length $n$ and was assigned an officer's task — to answer n questions. In the i-th question, it is required to determine the minimum number of elements from the array that need to be selected from the board (it is allowed to use the same element multiple times) so that their product is exactly equal to i, or to report that it is impossible to achieve such a product. Note that at least one element must be selected.

Input

Each test consists of several test cases. The first line contains one integer $t ( 1 \le t \le 10^4)$ — the number of test cases. The description of the test cases follows. The first line of each test case contains one integer $n (1 \le n \le 3 \cdot 10 ^ 5)$ . The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n (1 \le a_i \le n)$ . It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $3 \cdot 10 ^ 5$ .

Output

For the $i$-$th$ question, output one integer — the minimum number of elements from the array required to obtain a product equal to $i$ , or $−1$ if it is impossible to achieve such a product.

Example

Input

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

Output

-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

Note

Consider the first test case. The products can be obtained as follows:

• 1 cannot be obtained.

• 2 can be obtained by selecting $a_2$.

• 3 can be obtained by selecting $a_1$.

• 4 can be obtained by selecting $a_2$ twice.

• 5 cannot be obtained.

• 6 can be obtained by selecting $a_7$.

• 7 can be obtained by selecting $a_5$.

• 8 can be obtained by selecting $a_2$ three times.

中文翻译

E. 乘积查询 (Product Queries)

时间限制：3.0 秒
内存限制：256 兆字节
输入：标准输入
输出：标准输出

题目描述

今天，$Sabyrzhan$ 被叫到黑板前处理一个长度为 $n$ 的数组 $a$。他被分配了一个“任务”——回答 $n$ 个问题。

在第 $i$ 个问题中，需要确定：从数组中至少选择多少个元素（允许重复选择同一个元素），使得它们的乘积恰好等于 $i$。如果无法通过乘积得到 $i$，则输出 $-1$。

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

输入格式

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

接下来的测试用例描述如下：

1. 第一行包含一个整数 $n (1 \le n \le 3 \cdot 10^5)$。

2. 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n (1 \le a_i \le n)$。

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

输出格式

对于每个测试用例，输出 $n$ 个整数。第 $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 

样例解释

考虑第一个测试用例 ($n=8$, 数组为 $[3, 2, 2, 3, 7, 3, 6, 7]$)：

• 乘积 1：无法通过选择数组中的元素得到（即使选 $1$ 个也不行，因为数组中没有 $1$）。输出 -1。

• 乘积 2：选择 $a_2$。输出 1。

• 乘积 3：选择 $a_1$。输出 1。

• 乘积 4：选择 $a_2$ 两次 ($2 \times 2 = 4$)。输出 2。

• 乘积 5：无法得到。输出 -1。

• 乘积 6：选择 $a_7$。输出 1。

• 乘积 7：选择 $a_5$。输出 1。

• 乘积 8：选择 $a_2$ 三次 $(2 \times 2 \times 2 = 8)$。输出 3。

题解

思路

题目要求我们要合成 $1 \sim n$ 的每一个数，求最少需要几个原数组中的数相乘。

已知一些数字，如何通过乘法组合出目标数字，使得代价（使用的数字个数）最小。

状态定义： dp[i] 表示乘积恰好为 $i$ 时，所需的最少元素个数。 初始时，所有 dp[i] 设为无穷大。 对于输入数组中存在的数 x，dp[x] = 1（直接取它自己只要 1 个）。

状态转移： 我们可以从小到大枚举当前已经合成的数 $i$。如果 $i$ 是可达的，我们就尝试在 $i$ 的基础上再乘上一个原数组中的数 $k$，得到一个新的数 $j = i \times k$。 此时状态转移方程为： $dp[j] = \min(dp[j], dp[i] + 1)$ 其中 $k$ 必须是原数组中存在的数。

调和级数复杂度的枚举： 直接枚举 $i$ 和 $k$ 可能会比较慢。我们可以反过来思考（类似埃氏筛的思想）：

1. 外层循环枚举 $i$ 从 $1$ 到 $n$。

2. 如果 $dp[i]$ 是无穷大，说明 $i$ 目前无法合成，跳过。

3. 如果 $dp[i]$ 有值，我们枚举 $i$ 的倍数 $j （j = 2i, 3i, \dots 直到 n）$。

4. 计算倍率 $k = j / i$。如果 $k$ 在原数组中存在（即 st[k] == true），说明我们可以通过 $i$ 乘上 $k$ 得到 $j$。此时更新 dp[j]。

方法

1. 初始化： dp 数组初始化为无穷大。读取输入，如果数字 $x$ 存在，标记 st[x] = true 并将 dp[x] 设为 1。

2. 递推：

   • 遍历 $i$ 从 $1$ 到 $n$。

   • 若 $dp[i]$ 可达，则遍历其倍数 $j = i \times k$。

   • 若倍数 $k$ (也就是j/i) 在原数组中存在，则 dp[j] = min(dp[j], dp[i] + 1)。

3. 输出： 遍历 $1 \sim n$，如果 dp[i] 仍为无穷大，输出 $-1$，否则输出 dp[i]。

复杂度

时间复杂度：$O(N \log N)$。总循环次数为：$\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}$，调和级数，约等于$nlogn$。

空间复杂度：$O(N)$

代码实现

C++：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
​
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> dp(n + 1, 1e9); //dp[i]表示乘积为i时的最少元素个数，初始化为无穷大
        vector<bool> st(n + 1, false); //st[i]标记数字i是否在原数组中出现过
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            st[tmp] = true; //标记该数字存在
            dp[tmp] = 1;    //如果存在这个数字，该乘积只需要一个该数字
        }
        
        for (int i = 1; i <= n; i++) {
            if (dp[i] == 1e9) continue; //如果i不可达，就直接跳过
            
            //枚举i的倍数j
            for (int j = 2 * i; j <= n; j += i) {
                //j / i就是我们要乘的因子，如果这个因子在原数组中存在，说明可通过该因子乘当前数到达另一个数
                if (st[j / i]) {
                    dp[j] = min(dp[j], dp[i] + 1); //计算到达j的最短乘积路径长度
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            if (dp[i] == 1e9) {
                cout << -1 << " ";
            }
            else {
                cout << dp[i] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}