O - Sum + GCD (Hard)
Darjeeling
3
s
1024
MB
1300
点
問題文
長さ $N$ の正整数列 $A=(A_1, A_2, \ldots, A_N)$ が与えられます。$Q$ 個のクエリに答えてください。
$i$ 番目 ($1 ≤ i ≤ Q$) のクエリでは正整数 $K_i$ が与えられるので、以下の問題の答えを出力してください。
- $A$ の要素から ちょうど $K_i$ 個 を選び、選ばれた要素の総和を $S$ 、選ばれた要素の最大公約数を $G$ とします。 $S+G$ の値としてありうる 最大値 を求めてください。
制約
- 入力は全て整数
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^{18}\ (1\leq i\leq N)$
- $1 \leq Q\leq 2\times 10^5$
- $1 \leq K_i \leq N\ (1\leq i\leq Q)$
部分点
この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。
- ($100$ 点)
- $1\leq N\leq 100$
- $1 \leq A_i \leq 1000\ (1\leq i\leq N)$
- $Q=1$
- ($100$ 点)
- $1 \leq N\leq 10^4$
- $1 \leq A_i \leq 10^6\ (1\leq i\leq N)$
- $Q=1$
- ($500$ 点)
- $1 \leq A_i \leq 10^{12}\ (1\leq i\leq N)$
- $Q=1$
- ($600$ 点)
- 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$Q$
$K_1$
$\vdots$
$K_Q$
出力
$Q$ 行出力せよ。 $i$ 行目 $(1 ≤ i ≤ Q)$ には、$i$ 番目のクエリに対する答えを出力せよ。
答えは $64$ bit 整数に収まらない可能性があることに注意すること。
入力例 1
5
3 1 4 1 5
1
2
出力例 1
10
$A_3, A_5$ を選ぶと $S=9$ 、 $G=1$ 、 $S+G=10$ になります。ちょうど $2$ 個の要素を選ぶときこれが最大なので、$10$ を出力します。
この入力は、部分点 1., 2., 3., 4.の制約を満たします。
入力例 2
5
1 100 100 101 200
5
1
2
3
4
5
出力例 2
400
400
500
502
503
この入力は、部分点 4. の制約を満たします。
入力例 3
3
1000000000000 1000000000000 1000000000000
4
1
1
2
3
出力例 3
2000000000000
2000000000000
3000000000000
4000000000000
この入力は、部分点 4. の制約を満たします。
入力が $32$ bit 整数型に収まらない可能性や、出力が $64$ bit 整数型に収まらない可能性があることに注意してください。