/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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 の時の答えを出力せよ。
入力例 1
5 2 3 4 6 7 12
出力例 1
3 4 6 1 6
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 となり、これが最大です。
入力例 2
3 3 6 10 15
出力例 2
1 1 1
入力例 3
10 3 414003 854320 485570 52740 833292 625990 909680 885153 435420 221663
出力例 3
59 590 590 879 879 590 20 879 590 59
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 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(\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 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