JSOI2009:飞船燃料与瓶子的选择问题

宇航员jyy渴望返回地球，但他的飞船燃料不足。一次，他在向火星人请求燃料时，火星人同意了，但条件是以飞船上的瓶子交换。jyy的飞船上共有N个瓶子（1≤N≤1000），每个瓶子都有一定的容量Vi（1≤Vi≤1000000000）。经过谈判，火星人只需要K个瓶子（1≤K≤N）。这些瓶子没有刻度，只有瓶口标示了容量。火星人在收到瓶子后，不会完全装满所有瓶子，而是通过三种操作之一：1）装满某个瓶子；2）将某个瓶子中的燃料倒回燃料库；3）将燃料从一个瓶子倒入另一个瓶子，直至目标瓶子满或源瓶子空。jyy的目标是在选择K个瓶子的情况下，使火星人提供的燃料量最大。

第一行包含两个整数N和K。
接下来N行，每行包含一个整数Vi，表示第i个瓶子的容量。

输出一行，包含一个整数，表示火星人可能提供的最大燃料量。

选择第2个和第3个瓶子，火星人将被迫提供4单位的燃料。

根据裴蜀定理，如果存在两个瓶子容量x和y，那么可以通过上述操作获得的燃料量一定是ax+by的形式，其中a和b是整数。因此，能获得的最小正燃料体积是这两个容量的最大公约数。为了找到最大的燃料量，需要对所有瓶子的容量进行因数分解，并统计每个因数出现的次数。最后，选择出现次数大于等于K的第一个因数作为答案。

#include
#include
#include
using namespace std;
int n, k, x, tot, a[1000001], now, ans;
int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch <'0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = (x <<1) + (x <<3) + ch - '0'; ch = getchar(); }
    return x * f;
}
int main() {
    n = read(); k = read() - 1;
    while(n--) {
        x = read();
        for(int i = 1; i * i <= x; i++) {
            if(x % i == 0) {
                a[++tot] = i;
                if(i * i != x) a[++tot] = x / i;
            }
        }
    }
    sort(a + 1, a + tot + 1);
    for(int i = tot; i; i--) {
        if(i != tot && a[i] == a[i + 1]) now++;
        else {
            if(now >= k) {
                printf("%d\n", a[i + 1]);
                return 0;
            }
            now = 0;
        }
    }
    return 0;
}