codeforces1183F Topforces Strikes Back（约数/思维）

题目链接：codeforces1183F Topforces Strikes Back

题目思路：

分情况讨论，

1. 选一个数，一定是选最大的那个数，假设是 $x_1$。

2. 选两个数，再选的这个数一定是最大的不是 $x_1$ 的约数的数，假设是 $x_2$。

   证明：

   假设当前两个数是 $a$，$b$。

   1. 如果其中有一个是 $x_1$ 的约数，则用 $x_1$ 替换这个数。
   2. 如果两个都不是 $x_1$ 的约数，则用 $x_1$ 替换 $min(a,b)$。
   3. 如果两个都是 $x_1$ 的约数，有 $x/2+x/3<x$，则只取 $x_1$ 即可。

3. 选三个数，第三个数一定是最大的不是 $x_2$ 的约数的数，假设是 $x_3$。但从上面的证明可以看出，有 $x/2+x/3+x/5>x$，这个时候我们只要判断是否存在这种情况，取最大值就好了。

参考代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N], flag[3];
vector<int> v;
int main() {
   
    int t;
    cin >> t;
    while (t--) {
   
        int n; cin >> n;
        for (int i = 1; i <= n; i++) {
   
            cin >> a[i];
        }
        sort(a+1, a+1+n);
        int ans = a[n];
        for (int i = 1; i <= n; i++) {
   
            if (a[n] % a[i] != 0) v.push_back(a[i]);
            if (a[i] == a[n]/2 && a[n] % a[i] == 0) flag[0] = 1;
            if (a[i] == a[n]/3 && a[n] % a[i] == 0) flag[1] = 1;
            if (a[i] == a[n]/5 && a[n] % a[i] == 0) flag[2] = 1;
        }
        int len = v.size();
        if (len) ans += v[len-1];
        for (int i = len-2; i >= 0; i--) {
   
            if (v[len-1] % v[i] != 0) {
   ans += v[i]; break;}
        }
        if (flag[0] && flag[1] && flag[2]) ans = max(ans, a[n]*31/30);
        cout << ans << endl;
        memset(flag, 0, sizeof(flag));
        v.clear();
    }
    return 0;
}