Codeforces Round #766 (Div. 2)补题 E.Not Adding 数论GCD

题目大意

给定序列，包含个不同的整数。每次可以从序列中选择两个元素和(要求不位于序列中)，将他们从序列中删除，同时将插入序列中。求最大的操作次数。

思路

首先，原序列中任意数字的一定小于序列中的最大值，即，且对于操作后的子集仍然成立。

那么我们可以假设将中的所有数字都加入集合中来，然后判断每个数究竟能否出现在集合中。

考虑某个数如何出现在序列中：

1. 
2. （是通过操作得到的的子集中的元素）

那么显然第二种情况的是通过得到的，那么一定存在使得是的倍数。

所以我们可以枚举的所有倍数，对于每个存在于序列中的倍数求，如果最终的结果是，那么代表一定能被凑出来，也就是会以第二种方式出现在集合中。我们从统计所有满足条件的。

额外注意，因为第一种情况(本身存在于序列中)，所以在枚举的过程中一定会多统计个，所以最终结果减去个。

Accepted Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int a[N];

inline void solve(){
    int n = 0, maxx = -1, ans = 0; cin >> n;
    for(int i = 1; i <= n; i++){
        int x = 0; cin >> x;
        maxx = max(maxx, x), a[x]++;
    }
    for(int i = 1; i <= maxx; i++){
        int gcd = 0;
        for(int j = i; j <= maxx; j += i) 
            if(a[j]) gcd = __gcd(gcd, j);
        if(gcd == i) ans++;
    }
    cout << ans - n << endl;
}

signed main(){
    solve();
    return 0;
}