题解 P4963 【美樱的颜料】

· · 题解

一、朴素做法

先考虑确定了选择的第一个数 i。那么必须先选择 1 ~ n 中所有 i 的倍数，再选择 i 除自身外最大约数的倍数……依次类推，直到选完 m 个数。

所以需要预处理的是 1 ~ n 的除自身外最大约数，可以在线性筛素数的过程中求出。

令 f_i 表示 i 除自身外最大的约数，那么如果一个数是 f_i 的倍数，它在计算 i 的倍数的贡献时和计算 f_i 的倍数的贡献时都会被计算，所以要去重。

（假设 \lfloor \frac n {f_i}\rfloor< m，\lfloor \frac n {f_{f_i}}\rfloor\ge m）

总贡献=\lfloor \frac n i\rfloor\times i+\left(\lfloor \frac n {f_i}\rfloor-\lfloor \frac n i\rfloor\right)\times f_i+\left(m-\lfloor \frac n {f_i}\rfloor\right)\times f_{f_i}

\quad\quad\ \,=\lfloor \frac n i\rfloor\times (i-f_i)+\lfloor \frac n {f_i}\rfloor\times (f_i-f_{f_i})+m\times f_{f_i}

若 \lfloor \frac n {f_{...f_i}}\rfloor< m，\lfloor \frac n {f_{f_{...f_i}}}\rfloor\ge m（层数与上面的示例不同），计算方式是类似的。

然后只要暴力枚举选的第一个数即可

直接这样做空间会炸.但是在讲正解前还是看一下这个做法的参考代码吧：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N=10000010;

int n,m,p[N],f[N],tot,ans;
bool np[N];

int main()
{
    int i,j,temp;

    cin>>n>>m;

    for (i=2;i<=n;++i)
    {
        if (!np[i])
        {
            p[++tot]=i;
            f[i]=1;
        }
        for (j=1;j<=tot&&i*p[j]<=n;++j)
        {
            np[i*p[j]]=true;
            f[i*p[j]]=i;
            if (i%p[j]==0)
            {
                break;
            }
        }
    }

    for (i=1;i<=n;++i)
    {
        temp=0;
        for (j=i;;j=f[j])
        {
            if (n/j<m)
            {
                temp+=n/j*(j-f[j]);
            }
            else
            {
                temp+=m*j;
                break;
            }
        }
        ans=max(ans,temp);
    }

    cout<<ans;

    return 0;
}

这个做法的时间复杂度是 O(nloglogn) 的（后面的枚举部分复杂度实际上和埃氏筛一样，都是质因数个数和），空间大约需要50MB。

二、优秀做法

可以发现，f 数组占用了大量的内存（4\times 10^7\mathrm{B}\approx38\mathrm{MB}），有没有办法不把 f 存下来做这道题呢？

注意计算 f 的这个循环（也就是线性筛的循环）：

    for (i=2;i<=n;++i)
    {
        if (!np[i])
        {
            p[++tot]=i;
            f[i]=1;
        }
        for (j=1;j<=tot&&i*p[j]<=n;++j)
        {
            np[i*p[j]]=true;
            f[i*p[j]]=i;
            if (i%p[j]==0)
            {
                break;
            }
        }
    }

事实上我们虽然不能快速地求出任意一个 f_i ，但我们可以快速地求出满足 f_x=i 的所有 x。

先考虑 n=m 的情况，把所有数抽象成一棵树，以 f_u 为 u 的父亲， f_u 和 u 之间的边权为 \lfloor\frac n u\rfloor\times(u-f_u)，那么以某个数为第一个数的答案就是这个数到树根的距离。可以用dfs解决，用类似线性筛的方式找儿子。

若 n\ne m，考虑当前节点 u 以 ans_u 表示以 u 为第一个数的答案，若 \lfloor\frac n u\rfloor\ge m，则 ans_u=\lfloor\frac n u\rfloor\times m，否则，令 u 的父亲为 f_u，ans_u=ans_{f_u}+\lfloor\frac n u\rfloor\times(u-f_u)。仔细看看朴素算法的做法就能明白为什么是这样了。

总的时间复杂度是 O(n) 的，空间消耗只有不到 \rm 14MB。

参考代码：

#include <iostream>
#include <cstdio>

using namespace std;

const int N=10000010;

void dfs(int u,int fa,int sum);

int n,m,p[N/10],tot,ans;
bool np[N];

int main()
{
    int i,j;

    cin>>n>>m;

    for (i=2;i<=n;++i)
    {
        if (!np[i])
        {
            p[++tot]=i;
        }
        for (j=1;j<=tot&&i*p[j]<=n;++j)
        {
            np[i*p[j]]=true;
            if (i%p[j]==0)
            {
                break;
            }
        }
    }

    dfs(1,0,0);

    cout<<ans;

    return 0;
}

void dfs(int u,int fa,int sum)
{
    sum+=min(m,n/u)*(u-fa);
    ans=max(ans,sum);
    for (int i=1;i<=tot&&u*p[i]<=n;++i)
    {
        int v=u*p[i];
        if (n/v>=m)
        {
            dfs(v,0,0);
        }
        else
        {
            dfs(v,u,sum);
        }
        if (u%p[i]==0)
        {
            break;
        }
    }
}

三、优秀的dp做法和优化的朴素做法

这两种方法的核心思想是：最优的起点一定大于等于 \lfloor\frac n 2\rfloor+1，因为对于 u\le\lfloor\frac n 2\rfloor，f_{2u}=u，以 2u 为起点一定更优。

所以，可以得到下面的两种做法，压缩空间的核心都是只存一半，另一半直接更新答案而不保存，就不详细讲解了：

跑的飞快的dp做法：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N=10000010;

int n,m,p[N/10],f[N/2],tot,ans;

int main()
{
    int i,j,v;

    cin>>n>>m;

    ans=max(m,n+m-1);
    f[1]=m;

    for (i=2;i<=n/2;++i)
    {
        if (!f[i])
        {
            p[++tot]=i;
            if (n/i>=m)
            {
                f[i]=m*i;
            }
            else
            {
                f[i]=f[1]+n/i*(i-1);
            }
        }
        for (j=1;j<=tot&&i*p[j]<=n;++j)
        {
            v=i*p[j];
            if (v<=n/2)
            {
                if (n/v>=m)
                {
                    f[v]=m*v;
                }
                else
                {
                    f[v]=f[i]+n/v*(v-i);
                }
            }
            else
            {
                if (n/v>=m)
                {
                    ans=max(ans,m*v);
                }
                else
                {
                    ans=max(ans,f[i]+n/v*(v-i));
                }
            }
            if (i%p[j]==0)
            {
                break;
            }
        }
    }

    cout<<ans;

    return 0;
}

这个dp做法也是 O(n) 的，而且常数比dfs小。但是空间消耗略大一些。

loglog的做法：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N=10000010;

int n,m,p[N/10],f[N/2],tot,ans;

int main()
{
    int i,j,k,temp;

    cin>>n>>m;

    ans=max(m,n+m-1);

    for (i=2;i<=n/2;++i)
    {
        if (!f[i])
        {
            p[++tot]=i;
            f[i]=1;
        }
        for (j=1;j<=tot&&i*p[j]<=n;++j)
        {
            if (i*p[j]<=n/2)
            {
                f[i*p[j]]=i;
            }
            else
            {
                temp=0;
                for (k=i*p[j];;k=(k<=n/2?f[k]:i))
                {
                    if (n/k<m)
                    {
                        temp+=n/k*(k-(k<=n/2?f[k]:i));
                    }
                    else
                    {
                        temp+=m*k;
                        break;
                    }
                }
                ans=max(ans,temp);
            }
            if (i%p[j]==0)
            {
                break;
            }
        }
    }

    cout<<ans;

    return 0;
}

P.S. 为什么要加上

设现在已经使用了的颜料编号构成的集合为 A，若\ \exists\ i,\ j\notin A,\ i,\ j\in [1,\ n],\ gcd(A,\ i)>gcd(A,\ j)，那么就不能选择颜料 j。

这个限制呢？因为这并不是最优策略，如：14 7

按照这个限制，答案是 27 ：12 6 3 9 1 2 4

实际上，若没有这个限制，答案是 28 ：12 4 8 2 6 10 14

P.P.S. 造数据的时候没想好..m 都是在 1 ~ n 纯随机的，导致最优方案的第一个数大多都是 2 的次幂，以至于@小粉兔 用并不优秀的做法进行数据分治，对于无法通过的点只计算 2 的次幂通过了此题...事实上这题骗分不太好卡...更新了数据也不会太强吧.大家理解上面两种 O(n) 做法就好。

P.P.P.S. 所以说到底为什么要加上上述限制呢？因为没有这个限制的时候出题人不会复杂度正确的做法..然后有一位julao@zhoutb2333 赛时看掉了这个限制想出了一个非常优秀的做法：

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

int n,m;
map<pii,ll> f;
ll F(int x,int y){
    if(x==1)
        return y;
    if(f[{x,y}])
        return f[{x,y}];
    ll ret=0;
    for(int i=2,pos;i<=x;i=pos+1)
        pos=x/(x/i),ret=max(ret,F(x/i,min(y,x/i))*pos+y-min(y,x/i));
    return f[{x,y}]=ret;
}
int main(){
    cin>>n>>m;
    cout<<F(n,m)<<endl;
    return 0;
}