题目链接：
http://115.28.76.232/problem?pid=1153
题意：
从给定的n个数中取出k个数，使得他们的最大公约数最大，求这个最大的公约数
分析：
暴力分解不可取，我们能够得到最大公约数肯定在[1,mmax]之间(mmax为当中最大的元素)，因为mmax不大，
因此我们能够从大到小枚举公约数，然后统计它的倍数的个数是不是大于等于k。假设是的话那么这个数必定是最大的。
代码例如以下：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 10010; int a[maxn]; int main() { int n,k,t,x; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); memset(a,0,sizeof(a)); int mmax = 0; for(int i=0;i<n;i++){ scanf("%d",&x); a[x]++; if( x > mmax) mmax = x; } int ans; bool f=0; for(int i=mmax;i>=1;i--){ int cnt=0; for(int j=i;j<=mmax;j+=i){ cnt += a[j]; if(cnt>=k){ ans = i; f=1; break; } } if(f) break; } printf("%d\n",ans); } return 0; }
转载于:https://www.cnblogs.com/bhlsheji/p/5305096.html
