Luogu4571 [JSOI2009]瓶子和燃料（裴蜀定理）题解

前置芝士

裴蜀定理

若(a)，(b)是整数，且(gcd(a,b)=d)，那么对于任意的整数(x)，(y)，(ax+by)都一定是(d)的倍数，特别地，一定存在整数(x)，(y)，使(ax+by=d)成立。

推广: (a_1,a_2,a_3...a_n)为(n)个整数，(d)是它们的最大公约数，那么存在整数(x_1...x_n)使得(x_1 imes a_1+x_2 imes a_2+...x_n imes a_n=d)。

思路

根据裴蜀定理，外星人所给出的燃料数量为(k)个瓶子容积的(gcd)。因此问题就转化为：从(n)个数中选出(k)个数，使得它们的(gcd)最大。

我们可以将每个数的因数分解出来（并不只是质因数），记录每一个因子的出现次数，排序以后选出最大的出现次数(geq k)的就可以了。

另外，本题数值较大，需要开(map)。

参考代码

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

using namespace std;

const int maxn = 1e6 + 10;
int n,cnt,k;
struct Num{
    int val,num;
}p[maxn];
map<int,int> T;

bool cmp(Num x, Num y){return x.val > y.val;}

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++ i){
        int v; scanf("%d", &v);
        for(int j = 1; j * j <= v; ++ j){
            if(v % j == 0){
                if(!T[j]) T[j] = ++ cnt, p[cnt].val = j, p[cnt].num ++;
                else p[T[j]].num ++;
                int fff = v / j;
                if(fff == j) continue;
                if(!T[fff]) T[fff] = ++ cnt, p[cnt].val = fff, p[cnt].num ++;
                else p[T[fff]].num ++;
            }
        }
    }
    sort(p + 1, p + 1 + cnt, cmp);
    for(int i = 1; i <= cnt; ++ i)
        if(p[i].num >= k) return printf("%d
", p[i].val), 0;
    return 0;
}