P6786 「SWTR-6」GCDs & LCMs

题目链接

洛谷P6786

题意

从n个数种选取一些数字a1~aj，使得其对于任意数字i要么ai=max（a1.....aj），或者存在ak>ai且ak+ai+gcd(ak,ai)=lcm(ak,ai);

题解

凑了几个样例发现只有当ai/aj=2/3时，才能满足ak+ai+gcd(ak,ai)=lcm(ak,ai);
所以最大的情况分成两种：
1.最大值之和
2.各个链总和的最大值
所以对这两种情况进行遍历就能暴力出结果

AC代码

#include "bits/stdc++.h"

using namespace  std;

#define int long long
const int maxn=3e5+10;

inline int rd()
{
    int a;scanf("%lld",&a);return a;
}

int n;
int a[maxn];
unordered_map<int,int>mp;
signed main(){
    n=rd();
    for(int i=1;i<=n;i++){
        a[i]=rd();
        mp[a[i]]+=a[i];
    }
    sort(a+1,a+1+n);
    int maxx=-1;

    for(auto it = mp.begin(); it!=mp.end() ;it++){
        maxx=max(maxx,it->second);
    }

    int res=-1;
    int sum;int first=0;
    for(int i=1;i<=n;i++) {
        sum=0;
        if(a[i]%2==0){
            int tmp=a[i];
            while(mp[tmp/2*3]&&tmp%2==0){
                sum+=mp[tmp];
                tmp=tmp/2*3;
            }
            sum+=mp[tmp];
        }
        res=max(sum,res);
    }

    printf("%lld\n",max(maxx,res));
    return 0;
}