bzoj 2257: [Jsoi2009]瓶子和燃料【裴蜀定理+gcd】

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

所以最后能得到的最小燃料书就是gcd，所以直接对因数计数然后找最小的个数大于k的因数就是答案

#include<iostream>

#include<cstdio>

#include<map>

using namespace std;

const int N=1005;

int n,k,a[N],mx;

map<int,int>s;

int main()

{

	scanf("%d%d",&n,&k);

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

    {

        scanf("%d",&a[i]);

        mx=max(mx,a[i]);

        int j;

        for(j=1;j*j<a[i];j++)

			if(a[i]%j==0)

			{

				s[j]++;

				s[a[i]/j]++;

			}

        if(j*j==a[i])

			s[j]++;

    }

    map<int,int>::iterator it=s.end(),jt=s.begin();

    for(it--,jt--;it!=jt;it--)

		if(it->second>=k)

		{

			printf("%d\n",it->first);

			break;

		}

	return 0;

}

巴特西

bzoj 2257: [Jsoi2009]瓶子和燃料【裴蜀定理+gcd】

最新文章

热门文章