传送门

[]

题意

给你n个数，移除最少的数字使剩下的数字GCD大于初始GCD

思路

需要一点暴力的技巧，先求出初始GCD为g，并统计每个数字的个数这是减少复杂度的关键，令ans=0，我们从i=g+1开始枚举GCD为i的个数，进行统计每次更新ans=min(ans,n-cnt)

需要注意的是某个数的因子依然是那个数倍数的因子，如2 4 8.这样可以避免重复统计。具体看代码

代码

#include
    
     using namespace std;#define ll long longconst int maxn=1.5e7+5;int a[maxn],num[maxn];int main(){    int n,i,j,h;    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    //freopen("in.txt","r",stdin);    cin>>n;        int g,m=0,ans=n;    //  memset(a,0,sizeof(a));        for(i=1;i<=n;i++){            cin>>h;            if(i==1) g=h;            else g=__gcd(g,h);            num[h]++;            if(h>m) m=h;        }        //cout<
     
      <