本文主要是介绍裴蜀定理--bzoj2257，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
jyy就一直想着尽快回地球，可惜他飞船的燃料不够了。
有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy
的飞船上共有 N个瓶子(1<=N<=1000) ，经过协商，火星人只要其中的K 个 。 jyy
将 K个瓶子交给火星人之后，火星人用它们装一些燃料给 jyy。所有的瓶子都没有刻度，只
在瓶口标注了容量，第i个瓶子的容量为Vi（Vi 为整数，并且满足1<=Vi<=1000000000 ） 。
火星人比较吝啬，他们并不会把所有的瓶子都装满燃料。他们拿到瓶子后，会跑到燃料
库里鼓捣一通，弄出一小点燃料来交差。jyy当然知道他们会来这一手，于是事先了解了火
星人鼓捣的具体内容。火星人在燃料库里只会做如下的3种操作：1、将某个瓶子装满燃料；
2、将某个瓶子中的燃料全部倒回燃料库；3、将燃料从瓶子a倒向瓶子b，直到瓶子b满
或者瓶子a空。燃料倾倒过程中的损耗可以忽略。火星人拿出的燃料，当然是这些操作能
得到的最小正体积。
jyy知道，对于不同的瓶子组合，火星人可能会被迫给出不同体积的燃料。jyy希望找
到最优的瓶子组合，使得火星人给出尽量多的燃料。
Input
第1行：2个整数N,K，
第2..N 行：每行1个整数，第i+1 行的整数为Vi
Output
仅1行，一个整数，表示火星人给出燃料的最大值。
Sample Input
3 2
3
4
4
Sample Output
4
HINT
选择第2 个瓶子和第 个瓶子，火星人被迫会给出4 体积的容量。
由裴蜀定理我们可以知道，这道题其实就是求>=k个的最大因子
只需将所有的数因数分解，找到最大的因数满足个数>=k
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define maxn 1005
using namespace std;
int n,k,v[maxn],ans;
map<int,int>:: iterator it;
map<int,int>cnt;inline int rd(){int x=0; char c=' ';while(c>'9' || c<'0') c=getchar();while(c<='9' && c>='0') {x=x*10+c-'0'; c=getchar();}return x;
}int main()
{n=rd(); k=rd();for(int i=1;i<=n;i++)v[i]=rd();for(int i=1;i<=n;i++)for(int j=1;j<=sqrt(v[i]);j++){if(v[i]%j==0) cnt[j]++,cnt[v[i]/j]++;if(j*j==v[i]) cnt[j]--;}for(it=cnt.begin();it!=cnt.end();it++)if(it->second >=k) ans=max(ans,it->first);printf("%d",ans);return 0;
}这篇关于裴蜀定理--bzoj2257的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
