筑波大学プログラミングコンテスト2024
コンテスト日時
2024/11/17 (Su) 12:00 - 16:00

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)$

部分点

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

  1. ($100$ 点)
  • $1\leq N\leq 100$
  • $1 \leq A_i \leq 1000\ (1\leq i\leq N)$
  • $Q=1$
  1. ($100$ 点)
  • $1 \leq N\leq 10^4$
  • $1 \leq A_i \leq 10^6\ (1\leq i\leq N)$
  • $Q=1$
  1. ($500$ 点)
  • $1 \leq A_i \leq 10^{12}\ (1\leq i\leq N)$
  • $Q=1$
  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 整数型に収まらない可能性があることに注意してください。

提出
C++23 (g++ 12.2.0)