CF1603D题解

· · 题解

题意

记 c(l,r)=\sum\limits_{i=l}^r\sum\limits_{j=i}^r[\gcd(i,j)\ge l]。你可以将1\sim n 的n 个数分成 k 段 0=x_1<x_2<x_3<\cdots<x_k<x_{k+1}=n，最小化

\sum_{i=1}^{k}c(x_i+1,x_{i+1})

数据范围：n,k\le 10^5,T 组询问， T\le 3\times 10^5。

solution

一个暴力的 DP 做法是：设 f_{i,k} 表示前 i 个数分成 k 段的最小值。转移是

f_{i,k}=\min_{j=1}^i\{f_{j-1,k-1}+c(l,r)\}

边界：f_{i,0}=+\infin，f_{0,k}=0。

询问数很多，可以预处理出 DP 数组 O(1) 查询。

DP状态数是 O(n^2) 的，无法承受。观察 c(l,r) 的性质，发现 c(l,r)\ge r-l+1，也就是说 f_{n,k}\ge n。其次，c(l,2l-1)=(2l-1)-l+1=l，也就是说，若 n<2^k，一定可以把 n 分成若干段，满足 c(l,r)=r-l+1，即f_{n,k}=n(2^k>n)。剩下的需要考虑的 k 就是 O(\log n) 级别的了。

状态数没有太大的优化空间了，考虑优化 c(l,r) 的计算。大力推式子：

\begin{aligned} c(l,r)&=\sum_{i=l}^r\sum_{j=i}^r[\gcd(i,j)\ge l]\\ &=\sum_{k=l}^r\sum_{i=l}^r\sum_{j=i}^r[\gcd(i,j)= k]\\ &=\sum_{k=l}^r\sum_{i=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{r}{k}\rfloor}\sum_{j=i}^{\lfloor\frac{r}{k}\rfloor}[\gcd(i,j)=1]\\ &=\sum_{k=l}^r\sum_{j=1}^{\lfloor\frac{r}{k}\rfloor}\sum_{i=1}^j[\gcd(i,j)=1]\\ &=\sum_{k=l}^r\sum_{i=1}^{\lfloor\frac{r}{k}\rfloor}\varphi(i) \end{aligned}

记 s(n)=\sum_{i=1}^n\varphi(i)，即 \varphi 的前缀和。则

c(l,r)=\sum_{k=l}^rs(\lfloor\frac{r}{k}\rfloor)

预处理出 s(n) 之后即可 O(\sqrt{r}) 查询。实际上，c(l,r) 的计算复杂度大概是 O(\sqrt{r-l}) 的。或者可以 O(n\sqrt{n}) 预处理 O(1) 查询。

考虑优化 DP 转移。根据这个DP分段的形式，大胆猜测 c(l,r) 满足四边形不等式，那么这样DP转移就可以使用决策单调性优化转移了。c(l,r) 满足四边形不等式的证明如下：

设 l_1<l_2<r_1<r_2，我们需要证明 c(l_1,r_1)+c(l_2,r_2)\le c(l_1,r_2)+c(l_2,r_1)。

设 f(l,r,p)=\sum_{k=l}^p(\lfloor\frac{r}{k}\rfloor)，那么

\begin{aligned} c(l_1,r_2)+c(l_2,r_1)&=f(l_1,r_2,r_2)+f(l_2,r_1,r_1)\\ &=(f(l_1,r_2,l_2-1)+f(l_2,r_2,r_2))+(f(l_1,r_1,r_1)-f(l_1,r_1,l_2-1))\\ &=f(l_1,r_2,l_2-1)-f(l_1,r_1,l_2-1)+c(l_1,r_1)+c(l_2,r_2)\\ \end{aligned}

显然 f(l_1,r_2,l_2-1)\ge f(l_1,r_1,l_2-1)，得证。

剩下的部分可以使用1D1D决策单调性优化DP的常见套路（分治/单调队列）进行，可以参考本蒟蒻的博客。因为有 O(\log n) 层，每层的复杂度是 O(n\log n) 的，转移的时间复杂度是 O(n\log^2n) 的，加上预处理的复杂度，总时间复杂度 O(n\log^2n+n\sqrt{n}) ，空间复杂度 O(n\sqrt{n})。

实际上，采用分治做法，假设当前的转移区间是 [L,R]，当前需要寻找转移点的是 mid。首先O(\sqrt{r-l}) 求出 c(R+1,mid)，然后从 \min(mid,R) 到 L 枚举转移点 i，c(i,mid)=c(i+1,mid)+s(\lfloor\frac{mid}{i}\rfloor)。这个做法的时间复杂度不太好证，不过预处理跑的很快，而且代码复杂度很低，下面的代码正是这个写法。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,LOG=18;
inline int read(){
    int s=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    return s*f;
}
#define ll long long
const ll inf=1e18;
int prime[N],pcnt;
ll phi[N];
bool vis[N];
void init(int n){
    phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            prime[++pcnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=pcnt&&prime[j]*i<=n;++j){
            vis[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<=n;++i)phi[i]+=phi[i-1];
}
inline ll calc(int l,int r){
    ll ret=0;
    for(int i;l<=r;l=i+1){
        i=min(r/(r/l),r);
        ret+=1ll*phi[r/l]*(i-l+1);
    }
    return ret;
}
inline ll c(int l,int r){return phi[r/l];}
int T,n,k;
ll f[N][LOG];
void solve(int l,int r,int L,int R){
    if(l>r)return;
    int mid=(l+r)>>1;ll sum=calc(R+1,mid);
    int pos=0;ll mn=inf; 
    for(int i=min(mid,R);i>=L;--i){
        sum+=phi[mid/i];
        if(sum+f[i-1][k-1]<=mn){
            mn=sum+f[i-1][k-1];
            pos=i;
        }
    }
    f[mid][k]=mn;
    solve(l,mid-1,L,pos);
    solve(mid+1,r,pos,R); 
}
int main(){
    n=100000;init(n);
    for(int i=1;i<=n;++i)f[i][1]=(1ll*i*(i+1))>>1;
    for(k=2;k<=17;++k)
        solve(1,n,1,n);
    T=read();
    while(T--){
        n=read();k=read();
        if(k>=20||n<(1<<k)){
            printf("%d\n",n);
            continue;
        }
        printf("%lld\n",f[n][k]);
    }
    return 0;
}