[JSOI2009]瓶子和燃料

我们观察这个题面

发现

对于两个瓶子,他能够凑成的所有的数字是

\(x - ky\),\(2x - k'y\),\(3x - k''y\)

之后我们发现,这个和裴蜀定理的公式非常相似,而裴蜀定理的内容是

\(ax+by=c\)有解

当且仅当

\((a,b)|c\)

而题目中的火星人会给你最小化,所以对于两个瓶子,你的收益就是\((x,y)\)

我们类比推到\(k\)个瓶子

其实实际上就是讲将\(k\)个瓶子以此两两合并

所以题目转化成了

选出\(k\)个数,使得他们的\(gcd\)最大

这样的话

我们就要暴力枚举因子

用map记录出现次数更新答案就好了

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<map>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
map <int,int> m;
int n,k,ans;
inline int gcd(int x,int y){
    return y == 0 ? x : gcd(y,x % y);
}
inline void work(int x){
    for(int i = 1;1ll * i * i <= x;++i)
    if(x % i == 0){
        int r1 = x / i;
        int r2 = i;
        if(r1 == r2) --m[r1];
        int x1 = (++m[r1]);
        int x2 = (++m[r2]);
    //  printf("%d %d %d %d %d\n",x,r1,r2,x1,x2);
        if(x1 >= k) ans = max(ans,r1);
        if(x2 >= k) ans = max(ans,r2);
    }   
}
int main(){
    n = read(),k = read();
    for(int i = 1;i <= n;++i){
        int x = read();
            work(x);
    }
    printf("%d\n",ans);
    return 0;
}