[BZOJ 2257][Jsoi2009]瓶子和燃料

题目大意

有 N个瓶子(1<=N<=1000)中拿出K个用来装燃料, 火星人可以
1、将某个瓶子装满燃料；
2、将某个瓶子中的燃料全部倒回燃料库；
3、将燃料从瓶子a倒向瓶子b，直到瓶子b满或者瓶子a空。
K个瓶子内必须有燃料, 火星人会尽可能减少燃料总量, 问能得到最多燃料的瓶子组合。

解题报告

可以发现一个规律

两个瓶子a,b能达到不为0的最小容量为gcd(a,b)
解释: 瓶子见相互倾倒类似于gcd的辗转相除，只不过把取模运算换成了从A倒满B然后把B倒空 （好像没说清楚。。算了请自行脑补吧。。）
然后既然可以达到这么一个体积，那么可以把a,b两个瓶子看为一个体积为gcd(a,b)的瓶子
那么问题就变成了一个相同的子问题，就可以知道答案是把所有N个数中选K个数使得这K个数的gcd最大。

然后解法非常暴力。。每个数字的因子最多有2*sqrt(a)个,(其实数量是远远小于这个数的),可以搞出所有数的因子然后排个序统计出现次数大于等于K的最大因子就是答案。

但是Hineven很懒，写了个map代替排序……

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

std :: map<int, int> table;
int ans = 1;
int N, K;
void div(int num) {
    for(int i = 1; i*i<=num; i++)
        if(num%i == 0) {
            table[i]++;
            if(table[i] >= K) ans = std :: max(ans, i);
            table[num/i]++;
            if(table[num/i] >= K) ans = std :: max(ans, num/i);
        }

}
int main () {
    scanf("%d%d", &N, &K);
    for(int i = 1; i<=N; i++) {
        int a;
        scanf("%d", &a);
        div(a);
    }
    printf("%d\n", ans);
}