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+;

priority_queue<int> q;

int n,k,x;

int main()

{

    scanf("%d%d",&n,&k);

    while(n--)

    {

        scanf("%d",&x);

        for(int i=;i*i<=x;i++)

            if(x%i==)q.push(i),q.push(x/i);

    }

    while()

    {

        x=q.top();q.pop();int cnt=;

        while(q.top()==x&&q.size())q.pop(),cnt++;

        if(cnt>=k)

        {

            printf("%d",x);return ;

        }

    }

}

巴特西

bzoj2257瓶子和燃料

最新文章

热门文章