【题解】
需要用到裴蜀定理。
k个瓶子能倒出的燃料的最小值是这k个瓶子的容量的gcd. 那么原问题转化为在n个数中找到k个数使得它们的gcd最大。因为n的范围很小，所以对每个数求出所有因数并排序，最后找出现次数大于等于k的因数就是答案了。
#include<cstdio>#include<algorithm>#include<cmath>#define N 1000010#define rg registerusing namespace std;int n,k,a[N],tot,now,cnt;inline int read(){int k=0,f=1; char c=getchar();while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();return k*f;}inline bool cmp(int x,int y){return x>y;}int main(){n=read(); k=read();for(rg int i=1;i<=n;i++){int x=read();for(rg int j=1;j<=sqrt(x);j++)if(!(x%j)){a[++tot]=j;if(j!=x/j) a[++tot]=x/j;}}sort(a+1,a+1+tot,cmp);for(rg int i=1;i<=tot;i++){if(now!=a[i]) now=a[i],cnt=1;else cnt++;if(cnt>=k){printf("%d\n",a[i]);return 0;}}return 0;}
BZOJ 2257 ?[Jsoi2009]瓶子和燃料
原文地址：https://www.cnblogs.com/DriverLao/p/8494925.html