题解 P4963 【美樱的颜料】
ouuan
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;
}
```