记录编号	584867	评测结果	AAAAAAAAAA
题目名称	最大公约数	最终得分	100
用户昵称	黄天乐	是否通过	通过
代码语言	C++	运行时间	0.181 s
提交时间	2023-11-16 15:48:31	内存使用	8.59 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=1e6;
int n,maxx;
int k,cnt,ans=1e9;
int a[MAXN],num[MAXN];
bool vis[MAXN];
int gcd(int a,int b){
    if(b==0)return a;
    else return gcd(b,a%b);
}
int main(){
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxx=max(maxx,a[i]);
    }
    int g=0;
    for(int i=1;i<=n;i++){
        g=gcd(a[i],g);
    }
    for(int i=1;i<=n;i++){
        a[i]/=g;
        num[a[i]]++;
    }
    for(int i=2;i<=maxx;i++){
        int cnt=n;
        if(vis[i])continue;
        for(int j=1;j<=maxx/i;j++){
            vis[i*j]=1;
            cnt-=num[i*j];
        }
        ans=min(ans,cnt);
    }
    cout<<ans<<endl; 
    return 0;
}