计蒜客-2019 蓝桥杯国赛 B 组模拟赛-公约数

输入格式 第一行输入两个整数 n,k。 第二行输入n个整数ai 。

输出格式 输出一个整数。

数据范围

样例输入1 4 3 2 4 8 3 样例输出1 2

样例输入2 4 2 4 8 6 6 样例输出2 6

思路：我还做过一样的题，还写了博客51nod-1179 最大的最大公约数竟然又忘了QAQ,好吧，再写一遍。。。

对于最大公约数一定在 1-Max(数组最大值）中，因此可以由大到小遍历GCD,对于 GCD只要查找它的倍数是否存在m个即可。

Code:

#include<iostream> using namespace std; const int MAX_S=1e6+5; int n,m; int d[MAX_S]; int main() { ios::sync_with_stdio(false); cin>>n>>m; int Max=0,res=0; for(int i=0,x;i<n;++i) { cin>>x; ++d[x]; Max=max(Max,x); } for(int i=Max;i>0&&!res;--i) for(int j=i,s=0;j<=Max;j+=i) { s+=d[j]; if(s>=m){ res=i; break; } } cout<<res<<endl; return 0; }