[luogu4571 JSOI2009] 瓶子和燃料 (数论)

传送门

Solution

题目说的很迷，但可以发现两个瓶子互相倒最少是容积的gcd

那么题目就转化为求其中选k个瓶子gcd的最大值，这个可以分解因数，枚举因数得到

Code

//By Menteur_Hxy

#include <map>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define Re register

#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)

#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)

//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2?EOF:*p1++)

using namespace std;

typedef long long LL;

char buf[1<<21],*p1,*p2;

inline int read() {

	int x=0,f=1;char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

const int MAXN=1010,MAX=1e7;

int n,k,tot,ans;

int vis[MAX],a[MAX];

map<int,int> id;

int main() {

	n=read(),k=read();

	Fo(i,1,n) {

		int x=read(),sqr=sqrt(x);

		Fo(i,1,sqr) if(x%i==0) {

			if(!id[i]) id[i]=++tot,a[tot]=i;vis[id[i]]++;

			if(!id[x/i]) id[x/i]=++tot,a[tot]=x/i;vis[id[x/i]]++;

		}

	}

	Fo(i,1,tot) if(vis[i]>=k) ans=max(ans,a[i]);

	printf("%d",ans);

	return 0;

}