題目鏈接：D - Artistic Partition

題目大意：要求將 \([1,n]\) 分成 \(k\) 段，使得每段對應的 \(c(l,r)\) 之和最小，其中 \(c(l,r)=\sum_{i=l}^r\sum_{j=i}^r[\gcd(i,j)\ge l]\)。

首先注意到當 \(r<2l\) 時，\(c(l,r)=r-l+1\)。所以當 \(2^k-1\ge n\) 時答案即為 \(n\)。

考慮 \(\texttt{DP}\)，設 \(f_{i,j}\) 表示已經分了 \(i\) 段，段末為 \(j\) 的最小值，則轉移式為 \(f_{i,j}=\min\{f_{i-1,k}+c(k+1,j)\}\)。

考慮轉移過程中，每次 \(j-1\) 到 \(j\) 對每個 \(f_{i-1,k}+c(k+1,j)\) 造成的影響。需要快速維護每個 \(k\) 對應值的變化量，即 \(c(k+1,j)-c(k+1,j-1)\)，顯然這個值為 $\sum_{i=k+1}^{j} [\gcd(i,j)\ge k+1] $。

由于 \(i<j\) 時，\(\gcd(i,j)\le i\)，于是就相當于要對每個位置 \(k\) 加上 $\sum_{i=1}^{j} [\gcd(i,j)\ge k+1] $。進一步地，其實就是加上 \(j-\sum_{i=1}^{j} [\gcd(i,j)\le k]\)。眾所周知，\(\gcd(i,j)\) 的取值只可能是 \(j\) 的約數，那么把 \(j\) 的所有約數 \(d_i\) 求出來，每次將區間 \([d_{i},d_{i+1})\) 加上對應貢獻即可。初始貢獻為 \(j\)，當 \(i\) 每次加一時貢獻會減少 \(\varphi(\frac{j}{d_i})\)，這是與 \(j\) 取 \(\gcd\) 的值為 \(d_i\) 的方案數。處理完每個位置的變化量后，當前的全局最小值即為 \(f_{i,j}\) 的值。

時間復雜度方面，相當于在每一層轉移中，對于每對 \((j,d_i)\) 都要進行一次線段樹的區間加操作，那么顯然是一個 \(O(n\log^3n)\) 的復雜度。于是為了卡常，需要將這個區間加變成后綴加才可通過此題。

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define ls o<<1
#define rs o<<1|1
#define LL long long
int T,n,k,cnt,p[N],v[N],phi[N];
LL f[20][N];
vector<int>d[N];
struct rua
{
	LL tag,mn;
}t[N<<2];
void Build(int o,int l,int r,int i)
{
	t[o].tag=0;
	if(l==r){
		t[o].mn=f[i][l];
		return;
	}
	int mid=l+r>>1;
	Build(ls,l,mid,i);
	Build(rs,mid+1,r,i);
	t[o].mn=min(t[ls].mn,t[rs].mn);
}
void add(int o,int tl,int tr,int l,int r,int c)
{
	if(l<=tl && tr<=r){
		t[o].tag+=c;
		t[o].mn+=c;
		return;
	}
	int mid=tl+tr>>1;
	if(l<=mid)add(ls,tl,mid,l,r,c),t[rs].tag+=c,t[rs].mn+=c;
	else add(rs,mid+1,tr,l,r,c);
	t[o].mn=min(t[ls].mn,t[rs].mn)+t[o].tag;
}
void pretype()
{
	phi[1]=1;
	for(int i=2;i<N;i++){
		if(!v[i])p[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt && i*p[j]<N;j++){
			v[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++)
	for(int j=i;j<N;j+=i)
		d[j].push_back(i);
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<N;i++)f[1][i]=1ll*i*(i+1)/2;
	for(int i=2;i<=17;i++){
		LL v=0;
		Build(1,1,N-1,i-1);
		for(int j=1;j<N;j++){
			v+=j;
			for(auto k:d[j])add(1,1,N-1,k,N-1,-phi[j/k]);
			f[i][j]=v+t[1].mn;
		}
	}
}
int main()
{
	pretype();
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		if(k>20 || (1<<k)-1>=n)printf("%d\n",n);
		else printf("%lld\n",f[k][n]);
	}
}