蒜头君有n个数，他想要从中选出k个数，使得它们的最大公约数最大。
请你求出这个最大的最大公约数。
输入格式
第一行输入两个整数 。
第二行输入 个整数 。
输出格式
输出一个整数。
数据范围
样例输入1
4 3
2 4 8 3
样例输出1
2
样例输入2
4 2
4 8 6 6
样例输出1
6
思路：
因为每一个a[i] 的范围是<=1e6 ，那么我们可以枚举i从1~1e6，枚举n个数中，分别有多少个是i的倍数，
如果数量大于等于k个，那么这k个数的gcd就是i或者i的倍数，
那么我们维护每一次满足条件的最大的i，最后就是答案。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define rt return #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d\n",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), ‘\0‘, sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define db(x) cout<<"== [ "<<x<<" ] =="<<endl; using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ ll a[maxn]; int n; ll b[maxn]; int main() { //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin); //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout); gbtb; ll k; cin>>n>>k; repd(i,1,n) { cin>>a[i]; b[a[i]]++; } // b[j] 代表a数组中j的数量。 ll ans=0ll; repd(i,1,1000000) { ll num=0ll; for (int j = i; j<1e6; j+=i) { num+=b[j]; } if(num>=k) { ans=max(ans,1ll*i); } } cout<<ans<<endl; return 0; } inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ‘ ‘ || ch == ‘\n‘); if (ch == ‘-‘) { *p = -(getchar() - ‘0‘); while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) { *p = *p * 10 - ch + ‘0‘; } } else { *p = ch - ‘0‘; while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) { *p = *p * 10 + ch - ‘0‘; } } }
原文：https://www.cnblogs.com/qieqiemin/p/10914746.html
