【BZOJ2257】[JSOI2009]瓶子和燃料（数论）

题面

BZOJ

洛谷

题解

很明显就是从\(n\)个数里面选\(K\)个数让他们的\(gcd\)最大。

暴力找所有数的因数，拿个什么东西存一下就好了。

#include<iostream>

#include<cstdio>

#include<map>

using namespace std;

#define ll long long

#define MAX 1010

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,K,ans;

map<int,int> M;

int main()

{

	n=read();K=read();

	for(int i=1;i<=n;++i)

	{

		int x=read();

		for(int j=1;j*j<=x;++j)

			if(x%j==0)

			{

				++M[j];

				if(x/j!=j)++M[x/j];

			}

	}

	for(map<int,int>::iterator it=M.begin();it!=M.end();++it)

		if(it->second>=K)ans=max(ans,it->first);

	printf("%d\n",ans);

	return 0;

}