CodeForces 2193E: E. Product Queries

662 字

3 分钟

CodeForces 2193E: E. Product Queries

2026-02-01

次阅读

算法

CodeForces

/

算法

题目链接#

https://codeforces.com/problemset/problem/2193/E

题目大意#

题目描述#

给定一个长度为 $n$ 的数组 $a$ ( $1 \le a_i \le n$ )。你需要依次回答 $n$ 个问题。

对于第 $k$ 个问题（ $k$ 从 $1$ 到 $n$ ）：

目标：从数组 $a$ 中选择最少数量的元素，使得这些元素的乘积恰好等于 $k$ 。
规则：数组中的同一个元素可以被重复选择多次。
限制：至少需要选择 1 个元素。

输出要求#

对于每一个 $k \in [1, n]$ ，输出一个整数：

如果能凑出乘积 $k$ ，输出所需的最少元素个数。
如果无法凑出，输出 $-1$ 。

数据范围#

$1 \le t \le 10^4$ （测试用例数量）
$1 \le n \le 3 \cdot 10^5$
$1 \le a_i \le n$
所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$ 。

样例解释摘要#

假设 $n=8$ ，数组 $a = [3, 2, 2, 3, 7, 3, 6, 7]$ 。

目标 4：可以选择两个 $2$ （ $a_2$ 和 $a_3$ 或者重复选 $a_2$ ），乘积 $2 \times 2 = 4$ ，数量为 2。
目标 6：可以直接选一个 $6$ （ $a_7$ ），数量为 1。虽然也可以选 $2 \times 3$ ，但那需要 2 个数，不是最少。
目标 5：数组里没有 5，也无法通过组合得到 5，输出 -1。

解题思路#

核心算法：动态规划 (DP) + 调和级数复杂度优化。

预处理
- 使用一个标记数组 has[x] 记录数字 $x$ 是否出现在输入数组 $a$ 中。
状态定义
- 令 dp[i] 表示乘积恰好为 $i$ 所需的最少元素个数。
- 初始化：所有 dp[i] = INF。对于输入中存在的每个数 $x$ ，令 dp[x] = 1。
状态转移
- 从小到大枚举当前乘积 $i$ （从 $1$ 到 $n$ ）。
- 如果 dp[i] 可达（即 $\neq$ $\neq =$ INF），则尝试向后转移：
  - 枚举倍数：遍历 $j = 2i, 3i, \dots, n$ 。
  - 计算因子 $v = j / i$ 。
  - 判定与更新：如果因子 $v$ 存在于原数组中（即 has[v] 为真），则尝试更新： $dp[j] = \min(dp[j], dp[i] + 1)$
复杂度分析
- 核心在于双层循环：外层枚举 $i$ ，内层枚举 $i$ 的倍数。
- 总运算次数约为 $n(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}) \approx n \ln n$ 。
- 时间复杂度： $O(n \log n)$ ，在 $n=3 \cdot 10^5$ 时完全可以接受。

代码实现#

1
#include <iostream>
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int N=3e5+10;
5
const int INF = 1e9;
6
int T, n;
7
int a[N], dp[N], has[N];
8
void solve() {
9
   scanf("%d", &n);
10
   memset(has, 0, sizeof has);
11
   memset(dp, 0x3f, sizeof dp);
12
   for(int i=1;i<=n;i++) {
13
       scanf("%d", &a[i]);
14
       has[a[i]]=1;
15
       dp[a[i]]=1;
16
   }
17
   for(int i=1;i<=n;i++) {
18
       if(dp[i]==0x3f3f3f3f) continue;
19
       for(int j=2*i;j<=n;j+=i){
20
         int v=j/i;
21
         if(has[v]) dp[j]=min(dp[j], dp[i]+1);
22
       }
23
   }
24
   for(int i=1;i<=n;i++) {
25
       if(dp[i]==0x3f3f3f3f) printf("-1 ");
26
       else printf("%d ", dp[i]);
27
   }
28
   printf("\n");
29
}
30

31
int main() {
32
    int t;
33
    scanf("%d", &t);
34
    while (t--) {
35
        solve();
36
    }
37
    return 0;
38
}

“千里之行，始于足下。”

CodeForces 2193E: E. Product Queries

https://shenyize.com/solutions/codeforces/2193e/

作者

Shenyize

发布于

2026-02-01

许可协议

CC BY-NC-SA 4.0