计信选拔赛 E-gcd！！！
题目描述
链接：https://ac.nowcoder.com/acm/contest/13017/E
给定一个数组，可以往数组里添加一个数（不大于当前数组最大值），然后从中任选k个数，使得他们GCD（最大公因数）最大。
思路：
记录每一个数的因子出现的次数，取最大的因子且出现的次数大于等于k-1的，就是答案。暴力枚举。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int t,n,k,a[N],cnt[N];
int main()
{
cin>>t;
while(t--){
cin>>n>>k;
int mx=-1;
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++){
cin>>a[i];
mx=max(mx,a[i]);
for(int j=1;j*j<=a[i];j++){
if(a[i]%j==0){
cnt[j]++;//统计每个因子出现过的次数
if(j*j!=a[i]) cnt[a[i]/j]++;
}
}
}
int ans=0;
for(int i=1;i<=mx;i++){
// cout<<cnt[i]<<" ";
if(cnt[i]>=k-1) ans=i;//满足大于等于k-1的条件，就更新答案
}
cout<<ans<<endl;
}
} 
投递蚂蚁集团等公司10个岗位 >
