AtCoderBeginnerContest393——E-GCDofSubset补题+题解python

AtCoder Beginner Contest 393

E - GCD of Subset

Problem Statement

You are given a sequence A = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, \dots, A_N) A=(A1​,A2​,…,AN​) of length N N N and a positive integer K K K (at most N N N). For each i = 1 , 2 , … , N i = 1, 2, \dots, N i=1,2,…,N, solve the following problem:

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

问题陈述

给定一个长度为 N 的序列 A = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, \dots, A_N) A=(A1​,A2​,…,AN​) 和一个正整数 K (最多为 N )。

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

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

Constraints 1 ≤ K ≤ N ≤ 1.2 × 1 0 6 1 \leq K \leq N \leq 1.2 \times 10^6 1≤K≤N≤1.2×106 1 ≤ A i ≤ 1 0 6 1 \leq A_i \leq 10^6 1≤Ai​≤106All input values are integers.

所有输入值均为整数

Input

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

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

N N N K K K A 1 A_1 A1​ A 2 A_2 A2​ … \dots … A N A_N AN​

Output

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

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

Sample Input 1 5 2 3 4 6 7 12 Sample Output 1 3 4 6 1 6

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

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

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

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

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

对于 i = 5 i=5 i=5 ，选择 A 5 A_5 A5​ 和 A 3 A_3 A3​ 得到 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 x x only if:

A i A_i Ai​ is divisible by x x x. A A A has at least K K K elements divisible by x x x.

The answer is the maximum among such x x x.

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

t d = ∑ d ∣ n s n , t_d = \sum_{d \vert n} s_n, td​=d∣n∑​sn​,

so t n t_n tn​ can be computed in the manner of the following double for loops.

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

Finally, let u n u_n un​ be the answer for A i = n A_i = n Ai​=n. u n u_n un​ relates t n t_n tn​ 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 u_n un​ can be computed by the following double for loop. The complexity of this for statement is also O ( M log ⁡ M ) \mathrm{O}(M \log M) O(MlogM).

All that left is to compute u A i u_{A_i} uAi​​ for each i i i.

This way, the problem can be solved in a total of O ( N + M log ⁡ M ) \mathrm{O}(N + M \log M) O(N+MlogM) time and O ( N + M ) \mathrm{O}(N + M) 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 O ( N M + M log ⁡ M ) \mathrm{O}(N \sqrt{M} + M \log M) O(NM ​+MlogM),one with spacial complexity O ( M log ⁡ M ) \mathrm{O}(M \log M) O(MlogM).

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 x x ：

A i A_i Ai​ 能被 x x x 整除。

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

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

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

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

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

t d = ∑ d ∣ n s n , t_d = \sum_{d \vert n} s_n, td​=d∣n∑​sn​,

因此 t n t_n tn​ 可以用以下双‘ for ’循环的方式计算。

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

最后，设 u n u_n un​ 为 A i = n A_i = n Ai​=n 的答案。 u n u_n un​ 涉及 t n t_n tn​

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 u_n un​ 可以通过下面的双‘ for ’循环来计算。这个‘ for ’语句的复杂度也是 O ( M log ⁡ M ) \mathrm{O}(M \log M) O(MlogM) 。

剩下的就是为每个 i i i 计算 u A i u_{A_i} uAi​​ 。

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

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

-时间复杂度 O ( N M + M log ⁡ M ) \mathrm{O}(N \sqrt{M} + M \log M) O(NM ​+MlogM) ，

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

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

---

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

---

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

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

---

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

---

核心思路

目标：对于每个元素 ( A i A_i Ai​)，找到一个最大的数 ( d d d)，使得：

(d) 是 ( A i A_i Ai​) 的因数。数组中至少有 (K) 个元素是 (d) 的倍数。

关键观察：最大的 (d) 一定是 ( A i A_i Ai​) 的因数，且 (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 A_i Ai​) 的答案。

---

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