题目连接

https://codeforces.com/contest/1183/problem/F

解题思路

大致思路：

1.选一个数，必然选最大的数；
2.选两个数，最大的数+不为其约数的最大的数（下注证明）；
3.选三个数，要么是最大的数+不为其约数的最大的数+不为前面俩数约数的最大的数，要么是最大数/2+最大数/3+最大数/5。

证明1：

就很显然，选一个数，肯定选最大的；

证明2：

如果选的两个数中一个为最大的数，那么另一个一定不为其约数，所以要选不为其约数的最大的数；反之如果不选最大的数，那么两个数一定都要为其约数（你不选其约数的话为啥不把最大的选上呢？假如这两个数其中一个是约数一个不是，那你为什么不选上最大的数，再选刚刚那个不是其约数的数呢？）

证明3：

选三个数的话，很容易考虑到要选最大的数+不为其约数的最大的数+不为前面俩数约数的最大的数；至于选最大数/2+最大数/3+最大数/5，当存在这三个整数的情况下才能能这样选数。为什么选的是“最大数/2+最大数/3+最大数/5”而不是“最大数/2+最大数/3+最大数/6”又或者是“最大数/3+最大数/5+最大数/7”又或者是“最大数/2+最大数/3+最大数/7”呢？
下面一一说明：
先看“最大数/2+最大数/3+最大数/5”：
假设最大数为a，a/2+a/3+a/5=(31/30) * a > a，这种情况比单选a要大，所以有可能是答案，但是如果三个数的和比a都小，就完全没必要选。

再看“最大数/2+最大数/3+最大数/6”：
这挺明显不行，因为6的倍数也是3和2的倍数吧，要选的话肯定是重复的，不再赘述。

“最大数/3+最大数/5+最大数/7”和“最大数/2+最大数/3+最大数/7”
还是假设最大数为a，a/3+a/5+a/7=(71/105) * a < a，a/2+a/3+a/7=(41/42) < a，都比a小，没必要选；
多枚举几种有代表性的情况不难发现，只有“最大数/2+最大数/3+最大数/5”这种情况大于a，有可能被选。

证毕。

小技巧：

1.unique去重。
2.从大到小寻找。
3.更多小技巧在代码注释中

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
//vis表示a数组包括哪些数，因为数据规模不大，可以直接判断a中是否存在某个数 
int ans,n,t,a[N],vis[N],f;

bool cmp(int aa,int bb)
{
    return aa>bb;
}

int main()
{
    cin>>t;
    while(t--)
    {
        f=0;
        memset(a,0,sizeof a);
        memset(vis,0,sizeof vis);
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]]=1;
        //去重 
        int nn=unique(a+1,a+n+1)-a-1;
        sort(a+1,a+nn+1,cmp);
        ans=a[1];
        for(int i=1;i<=nn;i++)
        {
            if(a[1]%a[i])//找不为a[1]约数的最大的数 
            {
                ans=a[i]+a[1];
                for(int j=i+1;j<=nn;j++)//找不为a[1]和刚刚找到的那个数的约数的最大的数 
                if((a[1]%a[j]) && (a[i]%a[j])) 
                {
                    ans=a[1]+a[i]+a[j];
                    break;
                }
                f=1;
            }
            if(f) break;
        }
        //a%30==0 <=> a%2==0 && a%3==0 &&a%5==0 
        if(a[1]%30==0 && vis[a[1]/2] && vis[a[1]/3] && vis[a[1]/5]) 
        ans=max(ans,a[1]/2+a[1]/3+a[1]/5);
        cout<<ans<<endl;
    }    

    return 0;
}