bzoj2257瓶子和燃料

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2257

以两个瓶子为例，可以倒出它们的差，这是它们容量的gcd的倍数。

k个瓶子就可以倒出它们容量的gcd的倍数。

由裴蜀定理得可以倒出它们的gcd。所以找出k个数使它们的gcd最大。

一个很妙的方法：把每个容量因数分解，从大到小排序，第一个个数>=k的因数(最大的 >=k个容量拥有它的)就是答案。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e8+5;
priority_queue<int> q;
int n,k,x;
int main()
{
    scanf("%d%d",&n,&k);
    while(n--)
    {
        scanf("%d",&x);
        for(int i=1;i*i<=x;i++)
            if(x%i==0)q.push(i),q.push(x/i);
    }
    while(1)
    {
        x=q.top();q.pop();int cnt=1;
        while(q.top()==x&&q.size())q.pop(),cnt++;
        if(cnt>=k)
        {
            printf("%d",x);return 0;
        }
    }
}