Codeforces Round #511 (Div. 2) C. Enlarge GCD

链接：https://codeforces.com/contest/1047/problem/C

题意：给你n个数，删掉尽可能少的数，使公共gcd更大

题解：思想还是采用暴力枚举的思想，因为要使gcd更大，从gcd+1开始枚举，找出原序列中所有当前是gcd的倍数的数，最后n减去就是答案

代码：

 1 //#include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<vector>
 4 #include<stack>
 5 #include<string>
 6 #include<cstdio>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<map>
10 #include<set>
11 #include<cmath>
12 #include<iomanip>
13 #define inf 0x3f3f3f3f
14 using namespace std;
15 typedef long long ll;
16 const int M = int(1e7)*2 + 5;
17 int a[M],b[M];
18 int gcd(int a, int b)
19 {
20     return  b ? gcd(b, a % b) : a;
21 }
22 signed main()
23 {
24     int n; cin >> n;
25     int g;
26     int maxn = -1;
27     for (int i = 0; i < n; i++){
28         int x; cin >> x;
29         a[x]++;
30         if (i == 0)
31             g = x;
32         else
33             g = gcd(g, x);
34         maxn = max(maxn, x);
35     }
36     int ans = 0;
37     for (int i = g + 1; i <= maxn; i++){
38         if (!b[i]){
39             int cnt = 0;
40             for (int j = i; j <= maxn; j += i) {
41                 b[j] = 1;
42                 cnt += a[j];
43             }
44             ans = max(ans, cnt);
45         }
46     }
47     if (ans == 0) cout << -1 << endl;
48     else cout << n - ans << endl;
49     return 0;
50 }