题目连接

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;
}