如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
容易发现，若 $k>\log n$ 时 $f(n,k)=n$，因为我们可以划分出 $[1,1],[2,3],[4,7],\cdots,[2^{\lfloor\log n\rfloor},n]$ 个区间，使得答案为 $n$。
暴力 DP：$f_{n,k}=\min\limits_{i=0}^{n-1} f_{i,k-1}+c(i+1,n)$。
先考虑优化计算 $c(l,r)$ 的复杂度：
\[\begin{aligned} c(l,r)=&\sum\limits_{i=l}^r\sum\limits_{j=i}^r[\gcd(i,j)\ge l]\\ =&\sum\limits_{k=l}^r\sum\limits_{i=l}^r\sum\limits_{j=i}^r[\gcd(i,j)=k]\\ =&\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor\frac rk\rfloor}\sum\limits_{j=i}^{\lfloor\frac rk\rfloor}[\gcd(i,j)=1]\\ =&\sum\limits_{k=l}^r\sum\limits_{j=2}^{\lfloor\frac rk\rfloor}\sum\limits_{i=1}^{j}[\gcd(i,j)=1]\\ =&\sum\limits_{k=l}^r\sum\limits_{j=1}^{\lfloor\frac rk\rfloor}\varphi(j)\\ =&\sum\limits_{k=l}^rs(\lfloor\frac rk\rfloor) \end{aligned}\]我们现在可以通过数论分块 $O(\sqrt n)$ 求值 $c(l,r)$ 了。
我们预处理出对每个 $r$ 做后缀和，就可以 $O(1)$ 求值 $c(l,r)$ 了，空间复杂度 $O(n\sqrt n)$。
我们定义 $f(i,j,r)=\sum\limits_{k=i}^js(\lfloor\frac rk\rfloor)$。对于 $i\le j\le k\le l$，我们可以证明 $c(i,k)+c(j,l)\le c(i,l)+c(j,k)$。
\[\begin{aligned} c(i,l)+c(j,k)=&f(i,l,l)+f(j,k,k)\\ =&f(i,j-1,l)+f(j,l,l)+f(i,k,k)-f(i,j-1,k)\\ =&f(i,j-1,l)-f(i,j-1,k)+c(j,l)+c(i,k)\\ \ge &c(j,l)+c(i,k) \end{aligned}\]我们现在证明了 $c$ 满足四边形不等式，那么该 DP 具有决策单调性，直接分治优化就行了，复杂度 $O(nk\log n)$。
#include<iostream>
int n=1e5,k,cnt,p[100010],np[100010],sq[100010];
long long phi[100010],f[20][100010],s1[100010][320],s2[100010][320];
long long c(int l,int r){
if(l>r) return 1e16;
if(r/l<=sq[r]) return s1[r][r/l]-phi[r/l]*(l-1-r/(r/l+1));
else return s2[r][l];
}
void solve(long long *g,long long *f,int l,int r,int pl,int pr){
if(l>r) return;
int p=0,mid=(l+r)>>1;
f[mid]=1e16;
for(int i=pl;i<=pr;i++) if(g[i]+c(i+1,mid)<f[mid]) p=i,f[mid]=g[i]+c(i+1,mid);
solve(g,f,l,mid-1,pl,p),solve(g,f,mid+1,r,p,pr);
}
int main(){
std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
phi[1]=1;
for(int i=2;i<=n;i++){
if(!np[i]) p[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
np[i*p[j]]=1;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
for(int i=1;i<=n;i++) phi[i]+=phi[i-1];
for(int i=1;i<=n;i++){
for(int j=1;j*j<=i;j++){
s1[i][j]=s1[i][j-1]+phi[j]*(i/j-i/(j+1));
sq[i]=j;
}
s2[i][i/(sq[i]+1)+1]=s1[i][sq[i]];
for(int j=i/(sq[i]+1);j;j--){
s2[i][j]=s2[i][j+1]+phi[i/j];
}
}
for(int i=1;i<=n;i++) f[1][i]=c(1,i);
for(int i=2;i<=17;i++) solve(f[i-1],f[i],1,n,1,n);
int T;
std::cin>>T;
while(T--){
std::cin>>n>>k;
if(k>17) std::cout<<n<<'\n';
else std::cout<<f[k][n]<<'\n';
}
return 0;
}