【bzoj2257】【JSOI2009】瓶子和燃料

题意

??有$n$个瓶子，每个瓶子有一个容量$V_i$，从中选出$k$个
有三种操作：
①.往瓶子$a$中灌满水
??②.将水从$a$倒入$b$中，直到$a$空或者$b$满
??③.把瓶子$b$中的水倒光
对于选出的一组瓶子，尽量通过操作使得体积最小，求能够获得的最大体积的水

解法

数论：
其实经过手玩几个小样例可以发现，能得到的水就是选出的$k$个瓶子容量$V$的$gcd$，那么可以考虑求出$V_i$的所有因子，然后将这些因子排序，找到最大的满足出现次数$≥k$的因子即是答案
??证明：
??首先假设有两个瓶子，容量分别为$a$和$b$，那么显然有：
??这两个瓶子能够凑出的体积数必定可以表示为：$ax+by$（$x，y$为整数）
??根据裴蜀定理：若$a，b$是整数,且$gcd$（$a，b$）=$d$，那么对于任意的整数$x，y$，$ax+by$都一定是$d$的倍数，特别地，一定存在整数$x，y$，使$ax+by=d$成立
??因此$（a，b）|ax+by$，所以根据最小的要求，答案就是$（a，b）$

复杂度

O（$\sum^n_{i=1}\sqrt{V_i}+cntlogcnt$），cnt为质因子个数

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#define Lint long long int
using namespace std;
const Lint INF=0x3f3f3f3f;
const int MAXN=3010;
int q[MAXN*MAXN],cnt;
int n,k;
map<int,int> f;
int main()
{scanf("%d%d",&n,&k);for(int k=1,x;k<=n;k++){scanf("%d",&x);for(int i=1;i*i<=x;i++)if( x%i==0 ){q[++cnt]=i;if( i*i!=x )   q[++cnt]=x/i;}}sort( q+1,q+cnt+1 );int tmp=cnt;cnt=0;for(int i=1;i<=tmp;i++){q[++cnt]=q[i],f[q[cnt]]++;while( q[i+1]==q[cnt] && i+1<=tmp )   i++,f[q[cnt]]++;}for(int i=cnt;i>=1;i--)if( f[q[i]]>=k ){printf("%d\n",q[i]);break ;}return 0;
}