BZOJ2257 - [Jsoi2009]瓶子和燃料

2017/10/29

数学结论题,想了假做法。

题目

jyy就一直想着尽快回地球,可惜他飞船的燃料不够了。

有一天他又去向火星人要燃料,这次火星人答应了,要jyy用飞船上的瓶子来换。jyy 的飞船上共有 N 个瓶子(1 <= N <= 1000) ,经过协商,火星人只要其中的 K 个。 jyy 将 K 个瓶子交给火星人之后,火星人用它们装一些燃料给 jyy 。所有的瓶子都 没有刻度,只在瓶口标注了容量,第i个瓶子的容量为 Vi( Vi 为整数,并且满足 1 <= Vi <= 1000000000 ) 。

火星人比较吝啬,他们并不会把所有的瓶子都装满燃料。他们拿到瓶子后,会跑到燃料 库里鼓捣一通,弄出一小点燃料来交差。jyy 当然知道他们会来这一手,于是事先了解了火 星人鼓捣的具体内容。火星人在燃料库里只会做如下的 3 种操作:
1、将某个瓶子装满燃料
2、将某个瓶子中的燃料全部倒回燃料库
3、将燃料从瓶子 a 倒向瓶子 b ,直到瓶子 b 满或者瓶子 a 空
燃料倾倒过程中的损耗可以忽略。火星人拿出的燃料,当然是这些操作能得到的最小正体积。 jyy 知道,对于不同的瓶子组合,火星人可能会被迫给出不同体积的燃料。jyy 希望找到最优 的瓶子组合,使得火星人给出尽量多的燃料。

输出一个数,即这个最多燃料的数量。

做法

对于已经选 k 个瓶子,所能给出的燃料一定是这些瓶子的线性组合:

考虑贝祖定理的一般形式:

换句话说,仅有两个瓶子的时候,最小正体积是他们的 gcd

对于多个瓶子的时候,我们可以扩展这个结论。

所以说答案就是这 k 个瓶子的 gcd

解法也就显然了,读进来给统计每个数的因数,然后找一个出现次数不小于 K 的最大因数输出即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tr1/unordered_map>
#include <vector>
using namespace std;
using namespace tr1;
typedef long long LL;
const int SIZ = 2e6;

int N, K;
unordered_map<int, int> cnt;
vector<int> v;

void decomp(LL x) {
    int _ = sqrt(float(x));
    for(int i=1;i<=_;i++) {
        if(x % i == 0) {
            cnt[i]++, cnt[x / i]++, cnt[i] -= (i * i == x);
            if(cnt[i] == 1) v.push_back(i);
            if(cnt[x / i] == 1) v.push_back(x / i);
        }
    }
}

int main() {
    scanf("%d %d", &N, &K);

    LL x;
    for(int i=1;i<=N;i++) {
        scanf("%lld", &x);
        decomp(x);
    }

    sort(v.begin(), v.end());

    for(int i=v.size();i>=0;i--) {
        if(cnt[v[i]] >= K) {
            printf("%d\n", v[i]);
            return 0;
        }
    }
}