题解 P4571 【[JSOI2009]瓶子和燃料】

· · 题解

裴蜀定理 对任何整数a、b和它们的最大公约 数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.

感谢度娘

这是一道运用裴蜀定理的数论题，通过题意也可得知，火星人只会给你最少而又不为零的燃料。（火星人真的很强）

我们来模拟一下火星人倒燃料的过程：

样例：3 4 4

显然只有两种方案：3 4和4 4

3（①） 4（②）：把②倒入燃料，然后倒给①，把①倒掉，于是乎，只剩下②的1单位燃料。

4 4：由于火星人会给你燃料，所以无论怎么倒都会有一个瓶子有4单位燃料。

结论就显而易见了，其实就是要从n个数找出k个数，使最大公约数最大。

首先分解因数：


    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        for(j=1;j*j<=a[i];j++)
        {
            if(a[i]%j!=0) continue;
            if(!f[j]) p[++t]=j;//第一次进入，证明有此因数
            f[j]++;//能装的个数++ 
            if(!f[a[i]/j]) p[++t]=a[i]/j;//同上
            if(j*j!=a[i]) f[a[i]/j]++;
            //判相等，就是不重复加一个因数，因为只有一个瓶子
        }
    }

然后就把所有的因数枚举：

    for(i=1;i<=t;i++)
    {
        if(f[p[i]]>=k) ans=max(ans,p[i]);//不断地查找，找到最大的且因子数量大于要选择瓶子数的就更换最大值。
    }

最后进行输出，于是一行新鲜的代码出炉了：

#include<iostream>
using namespace std;
long long a[1010],f[10000010],p[10000010],t,ans;//a体积,f能装x体积的个数，p燃料 
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j*j<=a[i];j++)
        {
            if(!a[i]%j) continue;
            if(!f[j]) p[++t]=j;//第一次进入 
            f[j]++;//能装的个数++ 
            if(!f[a[i]/j]) p[++t]=a[i]/j;//同 
            f[a[i]/j]++;//同 
            if(j*j==a[i]) f[j]--;//判相等 
        }
    }
    for(int i=1;i<=t;i++)
    {
        if(f[p[i]]>ans) ans=max(ans,p[i]);//略 
    }
    cout<<ans<<endl;
}

于是就RE了

原因是因为开了了大量无用的空间，f、p数组中的一些空间不一定应用，造成了很大的空间浪费，而在空间限制的面前，数组已经不能满足我们的需要，我们需要用到映射器，也就是MAP，STL容器能够节省大量的空间，它在存入数据时会随数量的增加而增加，貌似是呈2^n递增的，所以它正是适合这道题的存储器（为什么要用这个名字啊）

#include<map>
#include<cstdio>
using namespace std;
int a[1010],p[5000010],t,ans;//a体积,f能装x体积的个数，p燃料
map<int,int>f; 
int max(int x,int y){
    return x>y?x:y;
}
int read()//快读根据自己需要酌情添加
{
    int x=0,y=1;char c=getchar();while(c<'0'||c>'9'){y=-y;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}
    return x*y;
}
int main()
{
    int n=read(),k=read(),i,j;
    for(i=1;i<=n;i++)
    {
        a[i]=read();
        for(j=1;j*j<=a[i];j++)
        {
            if(a[i]%j!=0) continue;
            if(!f[j]) p[++t]=j;//第一次进入 
            f[j]++;//能装的个数++ 
            if(!f[a[i]/j]) p[++t]=a[i]/j;//同 
            if(j*j!=a[i]) f[a[i]/j]++;//判相等 
        }
    }
    for(i=1;i<=t;i++)
    {
        if(f[p[i]]>=k) ans=max(ans,p[i]);//略 
    }
    printf("%d",ans);
    return 0;
;}

PS:map前一个定义是驱动，后一个是存储内容，比如说可以把f["apple"]=666,这种操作在正确定义的情况下是允许的。