ACdream OJ 1153 (k-GCD)

?

题意：

从给定的n个数中取出k个数，使得他们的最大公约数最大，求这个最大的公约数

?

分析：

暴力分解不可取，我们可以得到最大公约数肯定在[1,mmax]之间(mmax为其中最大的元素)，由于mmax不大，

因此我们可以从大到小枚举公约数，然后统计它的倍数的个数是不是大于等于k，如果是的话那么这个数必然是最大的。

?

代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      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
     
       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 ,ans); } return 0; } 
     
    
   
  

?

?