题解 | #[JSOI2009]瓶子和燃料#

一道考察公因数的题。
题意：
给你n个数，任取k个数，问他们的最大公因数的最大值。
思路：
因为题目给的n在1000左右，所以最开始我想用dp，后来发现行不通。
转念一想既然n这么小，那么在n*n^0.5的时间内枚举出所有数的因数是很轻松的。
顺带说一下为什么能在n^0.5的时间内枚举n的所有因数：因数都是成对出现的，若a为n的因数，那么
n/a也必定为n的因数，因此只要枚举1~n^0.5次方内的数就行了。（注意，若n为平方数则n^0.5会被枚举两次）

开一个map，对每一个数，若它在a[i]的因数中出现过就给它的计数值加一，如果计数值大于k而且原数值比当前答案大就更新当前最佳答案。

具体过程见代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
#define int long long
#define debug cout<<"***"<<endl;
using namespace std;</unordered_map></algorithm></cstdio></iostream>

int n,k;
unordered_map<int,int>mp;
signed main(){
cin>>n>>k;
int ans=0;
for(int i=1;i<=n;i++){
int t;
cin>>t;
for(int j=1;jj<=t;j++){
if(t%j==0){
if(++mp[j]>=k)
ans=max(ans,j);
if(jj!=t){
int s=t/j;
if(++mp[s]>=k)
ans=max(ans,s);
}
}
}
}
cout<<ans<<endl;
}