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

#include<bits/stdc++.h>
using namespace std;
int n,m,s,ans=0x3f3f3f3f;
int gcd(int x,int y){
        if(y == 0)return x;
        return gcd(y,x%y);
}
int a[1010000],v[1010000];
int main(){
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
      cin>>n;
      for(int i=1;i<=n;i++){
          cin>>a[i];
          
      }
      s=a[1];
      for(int i=1;i<=n;i++){
          s=gcd(s,a[i]);
          for(int j=1;j<=sqrt(a[i]);j++){
              if(a[i]%j==0){
                  v[j]++;
                  v[a[i]/j]++;
              }
          }
          if((int)sqrt(a[i])*(int)sqrt(a[i])==a[i]){
              v[(int)sqrt(a[i])]--;
          }
      }
     for(int i=s+1;i<=1e6;i++){
         ans=min(ans,n-v[i]);
     }
     cout<<ans;

}