【bzoj2257】[Jsoi2009]瓶子和燃料 扩展裴蜀定理+STL-map

题目描述

给出 $n$ 个瓶子和无限的水，每个瓶子有一定的容量。每次你可以将一个瓶子装满水，或将A瓶子内的水倒入B瓶子中直到A倒空或B倒满。从中选出 $k$ 个瓶子，使得能够通过这 $k$ 个瓶子凑出的最小体积最大。求这个体积。

输入

第1行：2个整数N,K，  
第2..N 行：每行1个整数，第i+1 行的整数为Vi

输出

仅1行，一个整数，表示火星人给出燃料的最大值。

样例输入

3 2 
3 
4 
4

样例输出

4

---

题解

扩展裴蜀定理+STL-map

显然通过容量为 $v_1,v_2,...,v_k$ 的瓶子能够凑出的容量 $c$ 满足：$v_1x_1+v_2x_2+...+v_kx_k=c$ 存在整数解。

根据裴蜀定理有 $\gcd(v_1,v_2,...,v_k)|c$ 。因此最小正整数就是它们的 $\gcd$ 。

原问题转化为：从 $n$ 个数中选出 $k$ 个，使得它们的 $\gcd$ 最大。

枚举所有数的所有约数，判断其是否是至少 $k$ 个数的约数，并更新答案即可。这个过程可以使用STL-map维护。

时间复杂度 $O(n\sqrt v+n\log n·约数个数)$ ，由于约数个数极少，远达不到 $\sqrt v$ ，因此可以通过。

#include <map>

#include <cstdio>

using namespace std;

map<int , int> mp;

map<int , int>::iterator it;

int main()

{

	int n , k , i , j , x , ans = 0;

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

	for(i = 1 ; i <= n ; i ++ )

	{

		scanf("%d" , &x);

		for(j = 1 ; j * j <= x ; j ++ )

		{

			if(x % j == 0)

			{

				mp[j] ++ ;

				if(j * j != x) mp[x / j] ++ ;

			}

		}

	}

	for(it = mp.begin() ; it != mp.end() ; it ++ )

		if(it->second >= k)

			ans = max(ans , it->first);

	printf("%d\n" , ans);

	return 0;

}