E - GCD of Subset

Contest Duration: 2025-02-15(Sat) 12:00 - 2025-02-15(Sat) 13:40 (local time) (100 minutes) Back to Home

E - GCD of Subset Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $475$ 点

問題文

長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ と $N$ 以下の正整数 $K$ が与えられます。
$i=1,2,\dots,N$ について次の問題を解いてください。

$A_i$ を含むように $K$ 個の要素を $A$ から選ぶ時、それらの最大公約数 (GCD) としてあり得る最大値を求めてください。

制約

$1 \leq K \leq N \leq 1.2 \times 10^6$
$1 \leq A_i \leq 10^6$
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

$N$ 行出力せよ。 $j$ 行目には $i=j$ の時の答えを出力せよ。

入力例 1Copy

Copy

5 2
3 4 6 7 12

出力例 1Copy

Copy

$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$ となり、これが最大です。

入力例 2Copy

Copy

3 3
6 10 15

出力例 2Copy

Copy

1
1
1

入力例 3Copy

Copy

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

出力例 3Copy

Copy

Score : $475$ points

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.

Constraints

$1 \leq K \leq N \leq 1.2 \times 10^6$
$1 \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$ .

Sample Input 1Copy

Copy

5 2
3 4 6 7 12

Sample Output 1Copy

Copy

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.

Sample Input 2Copy

Copy

3 3
6 10 15

Sample Output 2Copy

Copy

1
1
1

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy