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

AtCoder Beginner Contest 393

E - GCD of Subset

Problem Statement

You are given a sequence $A=(A_1,A_2,\dots ,A_N)$ of length $N$ and a positive integer $K$ (at most $N$).
For each $i=1,2,\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=(A_1,A_2,\dots ,A_N)$ 和一个正整数 K (最多为
N )。

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

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

Constraints

• $1\le K\le N\le 1.2\times 10^6$
• $1\le A_i\le 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

3
4
6
1
6

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

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

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

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

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

对于 $i=5$ ，选择 $A_5$ 和 $A_3$ 得到 gcd ⁡ ( { 12 , 6 } ) = 6 \gcd(\lbrace 12,6 \rbrace) = 6 gcd({12,6})=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

59
590
590
879
879
590
20
879
590
59

---

题解：

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 $M=\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 $d|n$ as “$d$ divides $n$. $t_n$ and $s_n$ have the relation

$$t_d=\sum _{d|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 ⁡ ( { d such that  d ∣ n and  t d ≥ K } ) , u_n =\max(\left\lbrace d \text{ such that }d \vert n\text{ and }t_d \geq K\right\rbrace), un​=max({d such that d∣n and td​≥K}),

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表。 $M=\max (A)$ 。

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

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

$$t_d=\sum _{d|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 ⁡ ( { d such that  d ∣ n and  t d ≥ K } ) , u_n =\max(\left\lbrace d \text{ such that }d \vert n\text{ and }t_d \geq K\right\rbrace), un​=max({d such that d∣n and td​≥K}),

所以 $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最大。

方法思路

1. 统计每个数的出现次数：我们首先统计每个数在数组中的出现次数。
2. 计算每个数的倍数数量：对于每个可能的数d，计算数组中能被d整除的元素的数量。
3. 预处理最大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])

---

. 更新u数组：

• 对于每个 (d) 的倍数 multiple，如果 u[multiple] 还未被设置（即初始值 0），则将 (d) 赋给它。
• 为什么需要 if u[multiple] == 0？
  因为更大的 (d’)可能已经处理过这些倍数，并设置了更大的值。此时不应覆盖。

---

为什么这是正确的？

• 覆盖性：所有可能的 (d) 都会被检查。
• 贪心保证最大性：从大到小遍历，确保第一个满足条件的 (d) 就是最大的可能值。
• 因数关系：每个数的因数一定小于或等于它本身，反向遍历确保优先处理更大的因数。

---

总结

• u数组的作用：记录每个数 (m) 的最大因数 (d)，使得 (d) 的倍数数量足够）。
• 反向遍历确保贪心：优先处理更大的 (d)，保证结果的最大性。
• 条件判断：仅在 u[multiple] 未被设置时更新，避免覆盖更大的 (d)。

通过这种方式，最终的 u[Ai] 就是每个元素 ($A_i$) 的答案。

---

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢