记录编号	584880	评测结果	AAAAAAAAAA
题目名称	最大公约数	最终得分	100
用户昵称	黄天宇	是否通过	通过
代码语言	C++	运行时间	0.202 s
提交时间	2023-11-16 17:39:21	内存使用	14.51 MiB

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int M=1e6+10;
int n;
int a[M];
int b[M];
int s;
int t[M];
bool c[M];
int ans;
int minx;
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;
    minx=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    s=gcd(a[1],a[2]);
    for(int i=3;i<=n;i++){
        s=gcd(s,a[i]);
    }
    for(int i=1;i<=n;i++){
        a[i]/=s;
        b[a[i]]++;
    }
    for(int i=2;i<=M;i++){
        if(c[i]) continue;
            int cnt=n;
        for(int j=1;j<=M/i;j++){
            c[i*j]=1;
            cnt-=b[i*j];
        }
        minx=min(minx,cnt);
    }
    cout<<minx<<endl;
    return 0;
}