原题链接：https://www.luogu.com.cn/problem/P6786
首先抛出两个显而易见的式子，对于任意正整数 $i,j,k$ 均有：
- $gcd(k imes i, k imes j) = k imes gcd(i,j)$
- $ ext{lcm}(k imes i, k imes j) = k imes ext{lcm}(i,j)$
很容易解释这两个式子的正确性，因为左式相当于两个数因子都多了一个 $k$，所以最大公约数、最小公倍数的值也肯定是原来的 $k$ 倍。
接下来就可以开始处理题面中的式子了（这里为了方便，将式子进行了移项）：
定义 $f(i,j)=i+j+gcd(i,j)- ext{lcm}(i,j)$。
也就是说若 $f(i,j)=0$ 则 $i+j+gcd(i,j)= ext{lcm}(i,j)$。
对于任意三个正整数 $k,x,y$，根据上面的结论就有
$$
egin{aligned}
f(k imes x,k imes y)
&= k imes x + k imes y + gcd(k imes x,k imes y)- ext{lcm}(k imes x,k imes y) \
&= k imes x+k imes y+k imesgcd(x,y)-k imes ext{lcm}(x,y)\
&= k imes f(x,y)\
end{aligned}$$
也就是对于任意正整数 $i,j,k$，如果满足 $f(i,j)=0$，那么也有 $f(k imes i,k imes j)=0$。
那代表着我们只需要讨论哪些互质的正整数对 $(i,j)$ 满足式子值为 $0$。
这样一来，条件就简化成：$i+j+1-i imes j=0$，因式分解一下就是 $(i-1)(j-1)=2$。
令 $ile j$，因为 $i,j$ 都是正整数，所以满足条件的只有一组解：
$$left{
egin{aligned}
i & = 2\
j & = 3\
end{aligned}
ight.
$$
也就是 $f(2,3)=0$。
而根据之前的结论，对于正整数 $k$ 均有 $f(2k,3k)=0$。
换句话说，对于正整数 $i,j (i le j)$ 有 $i+j+gcd(i,j)= ext{lcm}(i,j)$，当且仅当 $frac{i}{j}=frac{2}{3}$。
做到这里，题目就简化了许多：
从 $a$ 序列中找出若干个数，使得这些数中每个数要么是这些数中最大的，要么存在另一个数是自己的 $frac{3}{2}$ 倍，最后找到这些数和的最大值。
之后流程就很简单了，这里简单梳理一下：
- 将序列 $a$ 从小到大排序。
- 令 $dp_i$ 表示所有最大值为 $a_i$ 的选出序列中，这些数和（不包含自己）的最大值。
- 如果序列中第 $i$ 个数与它前面的数相同，那么 $dp_i=dp_{i-1}+a_{i-1}$。
- 否则，如果 $a_i$ 是 $3$ 的倍数，那么 $dp_i=dp_{a_{i imes 2/3}的位置}+a_{a_{i imes 2/3}的位置}$ 。
- 找到最大的 $dp_i+a_i$。
具体如何找到有序序列中某个数在序列中最后的位置，使用 STL 或 hash 都可以解决（以下代码使用 std::map）。
代码
#include <algorithm> #include <cstdio> #include <map> #define N 300010 typedef long long ll; using namespace std; int n, a[N]; bool b[N]; ll dp[N], ans; map <int, int> m; inline ll max(ll a, ll b){ return a > b ? a : b; } int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); std::sort(a + 1, a + n + 1); // 排序 for(int i = 1; i <= n; i++) m[a[i]] = i; for(int i = 1; i <= n; i++){ if(a[i] == a[i - 1]) dp[i] = max(dp[i], dp[i - 1] + a[i]); else if(a[i] % 3 == 0) dp[i] = dp[m[a[i] / 3 * 2]] + a[m[a[i] / 3 * 2]]; } for(int i = 1; i <= n; i++) ans = max(ans, dp[i] + a[i]); // 因为 a[i] 没有算进 dp[i]，所以最后需要加进去 printf("%lld ", ans); return 0; }