Description

jyy就一直想著盡快回地球，可惜他飛船的燃料不夠了。 有一天他又去向火星人要燃料，這次火星人答應了，要jyy用飛船上的瓶子來換。jyy的飛船上共有 N個瓶子(1<=N<=1000) ，經過協商，火星人只要其中的K 個 。 jyy將 K個瓶子交給火星人之后，火星人用它們裝一些燃料給 jyy。所有的瓶子都沒有刻度，只在瓶口標注了容量，第i個瓶子的容量為Vi（Vi 為整數，并且滿足1<=Vi<=1000000000 ） 。 火星人比較吝嗇，他們并不會把所有的瓶子都裝滿燃料。他們拿到瓶子后，會跑到燃料庫里鼓搗一通，弄出一小點燃料來交差。jyy當然知道他們會來這一手，于是事先了解了火星人鼓搗的具體內容。火星人在燃料庫里只會做如下的3種操作：1、將某個瓶子裝滿燃料；2、將某個瓶子中的燃料全部倒回燃料庫；3、將燃料從瓶子a倒向瓶子b，直到瓶子b滿或者瓶子a空。燃料傾倒過程中的損耗可以忽略。火星人拿出的燃料，當然是這些操作能得到的最小正體積。 jyy知道，對于不同的瓶子組合，火星人可能會被迫給出不同體積的燃料。jyy希望找到最優的瓶子組合，使得火星人給出盡量多的燃料。 

Input

第1行：2個整數N,K，  第2..N 行：每行1個整數，第i+1 行的整數為Vi  

Output

僅1行，一個整數，表示火星人給出燃料的最大值。

Sample Input

Sample Output

HINT

選擇第2 個瓶子和第 個瓶子，火星人被迫會給出4 體積的容量。 

Source

題解：gcd+map

我們先考慮火星人會怎么選擇。

首先裝入瓶子中的燃料可以再倒入燃料庫，他會給你盡可能少的燃料，所以最后一定只有一個瓶子中有燃料。否則可以選擇剩余燃料較多的瓶子倒入燃料庫。

然后考慮這一個瓶子會怎么選擇，操作三其實就是一個輾轉相除的過程，那么其實就是求兩個數的gcd，如果有多個瓶子的話，那么一定是k個瓶子的gcd，因為2個數gcd(x,y)一定大于等于三個數gcd(x,y,z)，所以我們現在的目標就是最大化gcd(ans[1],ans[2],...,ans[k])

怎么最大化呢？發現n好小啊，那么我們可以用mp記錄下每個因數的出現次數，即對于每個數因數分解。

最后查詢出現次數>=k的最大的因數。

#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<cstdio>#include<map>#define N 1003using namespace std;int n,k;int a[N];map<int,int> mp;int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&k);	mp.clear();	for (int i=1;i<=n;i++) scanf("%d",&a[i]);	for (int i=1;i<=n;i++) {	  for (int j=1;j*j<=a[i];j++) 	   if (a[i]%j==0) {	   	 mp[j]++;	   	 if (a[i]/j!=j) mp[a[i]/j]++;	   }	}	map<int,int>::iterator it;	for (it=mp.end();it!=mp.begin();it--){		if (it->second>=k) {			PRintf("%d/n",it->first);			break;		}	}}