自动搬运

查看原文

来自洛谷，原作者为

	ouuan 如果奇迹有颜色的话，那么其中之一必是橙色的吧。

搬运于2025-08-24 22:05:43，当前版本为作者最后更新于2018-11-03 23:09:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一、朴素做法

先考虑确定了选择的第一个数 $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;
}