P6786 「SWTR-6」GCDs & LCMs

小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。 他想从这些数中选出一些数 $b_1,b_2,\cdots,b_k$ 满足：对于所有 $i\ (1\leq i\leq k)$，$b_i$ 要么是序列 $b$ 中的最大值，要么存在一个位置 $j$ 使得 $b_j>b_i$ 且 $b_i+b_j+\gcd(b_i,b_j)=\mathrm{lcm}(b_i,b_j)$。 - 如果你不知道 $\gcd$ 和 $\mathrm{lcm}$ 是什么，可以点击最底部的「帮助/提示」部分的链接。 小 A 想让选出的数之和尽量大。请求出这个最大值。

无

无

**「样例 1 说明」** 可以选择 $b=\{2,3\}$，因为 $2+3+\gcd(2,3)=\mathrm{lcm}(2,3)$。 **「数据范围与约定」** **本题采用捆绑测试。** - Subtask 1（5 points）：$n\leq2$； - Subtask 2（20 points）：$n\leq 17$； - Subtask 3（15 points）：$a_i\leq 2\times 10^3$； - Subtask 4（15 points）：$n\leq 2\times 10^3$； - Subtask 5（10 points）：$n\leq 5\times 10^4$； - Subtask 6（10 points）：$a_i\leq 10^7$； - Subtask 7（25 points）：无特殊限制。 对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$，$1\leq a_i\leq 10^9$。 **「帮助/提示」** $\gcd$ 表示[最大公约数](https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308?fr=aladdin)，$\mathrm{lcm}$ 表示[最小公倍数](https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0/6192375?fr=aladdin)。 **「来源」** [【LGR-075】洛谷 8 月月赛 II Div.2 & SWTR-06 & EZEC Round 3](https://www.luogu.com.cn/contest/33190)。 idea & solution & data by [Alex_Wei](https://www.luogu.com.cn/user/123294)。