Topforces Strikes Back

做法

• 1.因为使得答案最大，一定是优先选大数，所以先排序
  因为数之间没有倍数关系，一定不能选重复的数字，所以可以去重
• 2.分类讨论：
  1）如果能选一个数，一定是最大的那个数
  2）如果能选两个数，一定是最大的那个数+与它不成倍数关系中最大的数
  证明：
  因为 如果不选最大的那个数一定会比第一种情况小
  3）如果能选三个数
  i)根据第二种情况的证明，如果在情况二的确定前两个数，第三个数符合关系，答案可能为三个数之和
  ii)因为 如果存在这种关系的存在，只要判断这几个数存在，答案也可能为这三个数之和
• 3.然后在这些符合的答案中取大值即可

代码

// Problem: Topforces Strikes Back
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/113786
// Memory Limit: 524288 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=200010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int a[N];
bool st[N];
int ans,m;

void get(){
    for(int i=1;i<m;i++){
        if(a[0]%a[i]){
            ans=a[0]+a[i];
            for(int j=i+1;j<m;j++){
                if((a[0]%a[j])&&(a[i]%a[j])){
                    ans=a[0]+a[i]+a[j];
                    return;
                }
            }
            return;
        }
    }
}

void solve(){
    int n;cin>>n;
    mst(st,0);
    _for(i,n) cin>>a[i],st[a[i]]=1;
    m=unique(a,a+n)-a;
    sort(a,a+m,greater<int>());

    ans=a[0];
    get();

    if(a[0]%30==0&&st[a[0]/2]&&st[a[0]/3]&&st[a[0]/5]) ans=max(ans,a[0]/2+a[0]/3+a[0]/5);
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;while(t--)
    solve();
    return 0;
}