当前位置：首页 > article >正文

AtCoder Beginner Contest 393 —— E - GCD of Subset 补题 + 题解 python

article 2025/2/21 23:16:46

AtCoder Beginner Contest 393

E - GCD of Subset

Problem Statement

You are given a sequence $(A_1, A_2, \dots, A_N)$ of length $N$ and a positive integer $K$ (at most $N$ ).
For each $\dots, N$ , solve the following problem:

When you choose $K$ elements from $A$ that include $A_i$ , find the maximum possible GCD (greatest common divisor) of those chosen elements.

问题陈述

给定一个长度为 N 的序列 $(A_1, A_2, \dots, A_N)$ 和一个正整数 K (最多为
N )。

对于每个 $\dots, N$ ，求解如下问题：

-当您从 A 中选择包含 $A_i$ 的 K 元素时，找出这些所选元素的最大可能GCD(最大公约数)。

Constraints

$\leq K \leq N \leq 1.2 \times 10^6$
$\leq A_i \leq 10^6$
All input values are integers.

所有输入值均为整数

Input

The input is given from Standard Input in the following format:

输入来自标准输入，格式如下：

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print $N$ lines. The $j$ -th line should contain the answer for $i = j$ .

打印 $N$ 行。第 $j$ 行应该包含 $i = j$ 的答案。

Sample Input 1

5 2
3 4 6 7 12

Sample Output 1

For $i = 1$ , choosing $A_1$ and $A_3$ yields $\gcd(\lbrace 3,6 \rbrace) = 3$ , which is the maximum.
For $i = 2$ , choosing $A_2$ and $A_5$ yields $\gcd(\lbrace 4,12 \rbrace) = 4$ , which is the maximum.
For $i = 3$ , choosing $A_3$ and $A_5$ yields $\gcd(\lbrace 6,12 \rbrace) = 6$ , which is the maximum.
For $i = 4$ , choosing $A_4$ and $A_2$ yields $\gcd(\lbrace 7,4 \rbrace) = 1$ , which is the maximum.
For $i = 5$ , choosing $A_5$ and $A_3$ yields $\gcd(\lbrace 12,6 \rbrace) = 6$ , which is the maximum.

对于 $i = 1$ ，选择 $A_1$ 和 $A_3$ 得到 $\gcd(\lbrace 3,6 \rbrace) = 3$ ，这是最大值。

对于 $i = 2$ ，选择 $A_2$ 和 $A_5$ 得到 $\gcd(\lbrace 4,12 \rbrace) = 4$ ，这是最大值。

对于 $i = 3$ ，选择 $A_3$ 和 $A_5$ 得到 $\gcd(\lbrace 6,12 \rbrace) = 6$ ，这是最大值。

对于 $i = 4$ ，选择 $A_4$ 和 $A_2$ 得到 $\gcd(\lbrace 7,4 \rbrace) = 1$ ，这是最大值。

对于 $i = 5$ ，选择 $A_5$ 和 $A_3$ 得到 $\gcd(\lbrace 12,6 \rbrace) = 6$ ，这是最大值。

Sample Input 2

3 3
6 10 15

Sample Output 2

1
1
1

Sample Input 3

10 3
414003 854320 485570 52740 833292 625990 909680 885153 435420 221663

Sample Output 3

题解：

E - GCD of Subset官方题解 by en_translator

One can make the GCD $x$ only if:

$A_i$ is divisible by $x$ .
$A$ has at least $K$ elements divisible by $x$ .

The answer is the maximum among such $x$ .

To process the conditions above, we precalculate several DP tables. Let $\max(A)$ .
Let $s_n$ be the number of occurrences of $n$ in $A$ . $s_n$ can be constructed in $\mathrm{O}(N + M)$ using an array to count the occurrences while scanning $A$ .
Next, let $t_n$ be the number of multiples of $n$ in $A$ . Here, we will use the notation $\vert n$ as “ $d$ divides $n$ . $t_n$ and $s_n$ have the relation

$t_d = \sum_{d \vert n} s_n,$

so $t_n$ can be computed in the manner of the following double for loops.

The complexity of this double for loop can be bounded by ( $M$ times) the so-called harmonic series, so the complexity is $\mathrm{O}(M \log M)$ .

Finally, let $u_n$ be the answer for $A_i = n$ . $u_n$ relates $t_n$ as

$u_n =\max(\left\lbrace d \text{ such that }d \vert n\text{ and }t_d \geq K\right\rbrace),$

so $u_n$ can be computed by the following double for loop. The complexity of this for statement is also $\mathrm{O}(M \log M)$ .

All that left is to compute $u_{A_i}$ for each $i$ .

This way, the problem can be solved in a total of $\mathrm{O}(N + M \log M)$ time and $\mathrm{O}(N + M)$ space, which is fast enough.

Sample code (C++)

As a side note, there are many alternative solutions, including:

one with time complexity $\mathrm{O}(N \sqrt{M} + M \log M)$ ,
one with spacial complexity $\mathrm{O}(M \log M)$ .

both solutions will meet the two-second time limit if your implementation is good enough, but especially the former is subject to TLE (Time Limit Exceeded), so please be careful.

只有在以下情况下才能制作GCD $x$ ：

$A_i$ 能被 $x$ 整除。
$A$ 至少有 $K$ 个元素可以被 $x$ 整除。

答案是这些 $x$ 中的最大值。

为了处理上述条件，我们预先计算了几个DP表。 $\max(A)$ 。

设 $s_n$ 为 $n$ 在 $A$ 中出现的次数。 $s_n$ 可以在 $\mathrm{O}(N + M)$ 中构造，使用数组来计算扫描 $A$ 时的出现次数。

接下来，设 $t_n$ 为 $A$ 中 $n$ 的倍数个数。这里，我们将使用 $\vert n$ 作为“ $d$ 除以 $n$ ”。 $t_n$ 和 $s_n$ 有关系

$t_d = \sum_{d \vert n} s_n,$

因此 $t_n$ 可以用以下双‘ for ’循环的方式计算。

这个双‘for’循环的复杂度可以用( $M$ 倍的所谓的调和级数来限定，所以复杂度是 $\mathrm{O}(M \log M)$ 。

最后，设 $u_n$ 为 $A_i = n$ 的答案。 $u_n$ 涉及 $t_n$

$u_n =\max(\left\lbrace d \text{ such that }d \vert n\text{ and }t_d \geq K\right\rbrace),$

所以 $u_n$ 可以通过下面的双‘ for ’循环来计算。这个‘ for ’语句的复杂度也是 $\mathrm{O}(M \log M)$ 。

剩下的就是为每个 $i$ 计算 $u_{A_i}$ 。

这样，总共可以在 $\mathrm{O}(N + M \log M)$ 时间和 $\mathrm{O}(N + M)$ 空间内解决问题，速度足够快。

作为旁注，有许多替代解决方案，包括：

-时间复杂度 $\mathrm{O}(N \sqrt{M} + M \log M)$ ，

-具有空间复杂度 $\mathrm{O}(M \log M)$ 。

如果你的执行足够好，两种方案都可以满足2秒的时间限制，但特别是前者会受到TLE（时间限制超出）的限制，所以请小心。

~~有点抽象，看不懂官方题解~~
~~接下来是我奶奶都能看懂的版本~~

为了解决问题，我们要找到一个包含给定元素 $A_i$ 的K个元素的子集，使得这些元素的GCD最大。

方法思路

统计每个数的出现次数：我们首先统计每个数在数组中的出现次数。
计算每个数的倍数数量：对于每个可能的数d，计算数组中能被d整除的元素的数量。
预处理最大GCD：从最大的数开始，检查每个数的倍数数量是否满足要求，并记录每个数的最大GCD。

t 数组的定义

$t$ 数组：t[d]是数组中能被d整除的元素的个数

u数组的定义

u[m]：对于数 (m)，它的值是所有满足以下条件的 (d) 中的最大值：
- (d) 是 (m) 的因数
- 数组中有至少 (K) 个元素是 (d) 的倍数

核心思路

目标：对于每个元素 ( $A_i$ )，找到一个最大的数 ( $d$ )，使得：
1. (d) 是 ( $A_i$ ) 的因数。
2. 数组中至少有 (K) 个元素是 (d) 的倍数。
关键观察：最大的 (d) 一定是 ( $A_i$ ) 的因数，且 (t[d] >= k )。我们需要找出所有满足条件的 (d)，并取最大的那个。

code：

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = Counter(a)

max_m = max(a)
# 计算t数组：t[d]是数组中能被d整除的元素的个数
t = [0] * (max_m + 1)
for d in range(1, max_m + 1):
    for multiple in range(d, max_m + 1, d):
        t[d] += s[multiple]

# 计算u数组：u[m]是m的最大因数d，满足t[d]>=k
u = [0] * (max_m + 1)
# 从大到小遍历d
for d in range(max_m, 0, -1):
    if t[d] >= k:
        for multiple in range(d, max_m + 1, d):
            if u[multiple] == 0:
                u[multiple] = d

# 输出每个元素的答案
for i in a:
    print(u[i])