传送门

这道题其实乍一看很难，但其实就是一道推数学规律的题，只要把这个规律推出来了，剩下的也就很好办了。

最关键的就是题面中所给的那个式子，bi+bj+gcd⁡(bi,bj)=lcm⁡(bi,bj)b_i+b_j+\gcd(b_i,b_j)=\operatorname{lcm}(b_i,b_j)，我们令 x=gcd⁡(bi,bj)x=\gcd(b_i,b_j)，pi=bi÷xp_i=b_i\div x，pj=bj÷xp_j=b_j\div x，则根据最小公因数和最大公倍数的定义可以得到：

pi⋅x+pj⋅x=x⋅pi⋅pj−xpi+pj=pi⋅pj−1pi⋅pj−pi−pj+1=2(pi−1)⋅(pj−1)=2p_i\cdot x+p_j\cdot x=x\cdot p_i\cdot p_j-x\\ p_i+p_j=p_i\cdot p_j-1\\ p_i\cdot p_j-p_i-p_j+1=2\\ (p_i-1)\cdot(p_j-1)=2

很明显可以知道

pi∈N+,pj∈N+p_i\in \mathbb{N_+},p_j\in\mathbb{N_+}

于是就可以推出

pi=2,pj=3p_i=2,p_j=3

所以

bi:bj=2:3b_i:b_j=2:3

也就是说，对于一个数，要么它是序列中最大的那个，要么就有另外一个数是它的 32\dfrac{3}{2} 倍。

因此，对于选出来的序列 b1,b2,b3,⋯ ,bkb_1,b_2,b_3,\cdots,b_k，将其去重并从小到大排序后，应该满足 32bi=bi+1\dfrac{3}{2}b_i=b_{i+1}，也就是一个公比为 32\dfrac{3}{2} 的等比数列，至于为什么是去重后，因为我们只关心这个数有没有比它大 12\dfrac{1}{2} 的数，只要满足这个条件，无论有几个和这个数相同的数，我们都可以把它们放在序列里面，比如 2,2,2,3,32,2,2,3,3 这个序列就是满足条件的。

这样，问题就转化成了，在给定序列中寻找一个公比为 32\dfrac{3}{2} 的等比序列，并且这个序列中所有数的和最大。对于这个问题，我的思路是 DP，先对原序列进行排序和去重，用 fif_i 表示以第 ii 个数结尾的公比为 32\dfrac{3}{2} 的等比数列中所有数的最大的和，状态转移方程也很好想，就是对于 aia_i，找有没有 aj=23aia_j=\dfrac{2}{3}a_i，如果有，那么 fi←fj+fif_i\leftarrow f_j+f_i，如果没有，就不管它，由于事先已经对序列排序并去重，所以这个找的过程可以用二分解决（别跟我说桶排，10910^9 的值域你自己去排），时间复杂度为 O(nlog⁡n)O(n\log n)，对付 3×1053\times 10^5 的数据也够了。

至于预处理，在去重的时候顺便解决一下就好了，具体的可以看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
int n,k,a[300001],b[300001];//a 是原数组，b 是去重后的数组
long long ans,f[300001];
int check(int l,int r,int val)//二分查找，如果有值为 val 的数则返回下标，没有则返回 -1
{
	while(l<=r)//记得一定要有等于！！！
	{
		int mid=(l+r)/2;
		if(b[mid]==val)
			return mid;
		if(b[mid]>val)
			r=mid-1;
		if(b[mid]<val)
			l=mid+1;
	}
	return -1;
} 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+1+n);//排序
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=a[i-1])//去重
			b[++k]=a[i];
		f[k]+=a[i];//预处理，如果和上一个数相同，就自动加到一起
	}
	for(int i=1;i<=k;i++)
	{
		if(b[i]%3==0)//一定要有这个条件！
		{
			int t=check(1,i,b[i]/3*2);
			if(t!=-1)
				f[i]+=f[t];
		}
		ans=max(ans,f[i]);
	}
	printf("%lld",ans);
	return 0;
}