分数: 475 点
问题陈述
给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 N 和一个正整数 K (最多 N).
对于每个 i = 1, 2, \dots, N,解决以下问题:
- 当您选择 K 元素来自 A 包括 A_i,找到这些所选元素的最大可能 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