bzoj 2257: [Jsoi2009]瓶子和燃料

.

题意：n个瓶子中选k个使倒出来的油的最小值最大。
题解：根据裴蜀定理，几个瓶子倒出来的油的最小值肯定是这些瓶子容量的最大公约数。我们标记一下每个瓶子的约数，最大的超过k个的就是答案。
代码：

#include<cstdio>
#include<cstring>
#include<map>
using namespace std;

int n,k;
map<int,int>a;

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        for(int j=1;j*j<=x;j++)
        {
            if(x%j==0)
            {
                a[j]++;
                if(j*j!=x)
                a[x/j]++;
            }
        }
    }
    for(map<int,int>::reverse_iterator it=a.rbegin();it!=a.rend();it++)
    if(it->second>=k)
    {
        printf("%d",it->first);
        break;
    }
}