题意
给你n个数，删除最少的数，使得剩余的数的最大公约数大于原来n个数的最大公约数
题目分析
普通解法
先求出所有数的最大公约数g,然后判断所有的数是否完全相同，完全相同说明最大公约数就是自身，无法增大，即无解
然后枚举公约数i , 从g+1开始，直到最大的数a[n]，统计因子含有 i 的数的个数，那么公约数为 i 的数集的其中一个公约数就是i，
即其最大公约数 >= i > g，因此这些数组成的集合就是最大公约数大于g的数集
而我们需要找的是这样的数集中的最大者，因为这样可以删除最少的数得到
优化解法
因为所有的数的最大公约数为g，那么对所有的数除g，得到的新的数集的最大公约数就会是1
统计每个数i出现的次数num[i]，如果num[1] = n ，说明所有数相同，与上面一样，此时无解
然后我们在新的数集中枚举公约数 i ，统计因子含有i的数的个数，那么公约数为i的数集的一个公约数将会是i，
即其最大公约数一定 >= i > 1，在原数集中满足最大公约数 >= i > g，因此公约数为i的数集就是最大公约数大于g的数集
同理，我们需要找的是这样的数集中的最大者，因为这样可以删除最少的数得到
优化方法
注意到我们枚举公因数的时候，以x作为公约数的数集一定比以x*k(k = 2, 3,4...)作为公约数的数集大，为此我们只需要找到公约数为素数的数集中的最大者即可。
考虑到这个题数据最大值在 1.5e7，如果使用一般的素数筛，肯定会T，为此，我们需要使用线性筛来求素数。
代码区
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<string> #include<cmath> #include<fstream> #include<vector> #include<stack> #include <map> #include <iomanip> #define bug cout << "**********" << endl #define show(x,y) "["<<x<<","<<y<<"]" //#define LOCAL = 1; using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int mod = 1e8; const int Max = 1.5e7 + 10; int n, a[300010], num[Max]; //num[i]表示 a/gcd 后的新数集中，值等于i的数的个数 int prime[Max], tot; //记录素数和素数的个数 bool vis[Max]; //记录是否是素数，用于线性筛 void getPrime() { memset(vis, 0, sizeof(vis)); tot = 0; for (int i = 2; i < Max;i++) { if (!vis[i]) prime[++tot] = i; for (int j = 1;i * prime[j] < Max; j++) { vis[i*prime[j]] = true; if (i % prime[j] == 0) break; } } } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif getPrime(); while (scanf("%d", &n) != EOF) { memset(num, 0, sizeof(num)); int g = 0; for (int i = 1; i <= n; i++) { scanf("%d", a + i); g = gcd(a[i], g); } for (int i = 1; i <= n;i++) { num[a[i] / g] ++; } if (num[1] == n) //所有数相等，就是无解 { printf("-1 "); continue; } int ans = n - 1; //记录最小删除个数 for (int i = 1;i <= tot; i++) //找到所有以prime[i]为因子的的数的个数，这些数的集合就是以prime[i]为公约数的数集 { int sum = 0; //记录这个数集的大小 for (int k = 1; k * prime[i] < Max; k++) { sum += num[k*prime[i]]; } ans = min(ans, n - sum); } printf("%d ", ans); } return 0; }