Artistic Partition

题解

看到这种统计最小值的题应该很容易想到 $d p$ ，我们可以记 $dp_{i,j}$ 表示划分到点 $i$ ，已经划分了 $j$ 块，但如果直接进行 $d p$ 转移的话显然会 $T$ 。
但我们可以猜测到一点，当 $K$ 比较大的时候，我们应该很容易划分这个序列使得每个数在其区间中，与除自己外的所有数的 $\gcd$ 都不大于改区间的 $l$ 。
也就是说我的的答案就为 $n$ 。
有了这个结论，我们就可以去想想怎么划分。
一个区间 $[l, r]$ 第一个会使得 $\gcd(l,r)\geqslant l$ 的数对显然是 $(l, 2 l)$ ，也就是说，如果我们的 $r < 2 l$ ，改区间答案便为 $r ? l + 1$ 。
容易发现，这样的话，只要我们的 $2^k>n$ ，就答案就为 $n$ 。也就是说，我们需要 $d p$ 的 $K$ 是 $\log n$ 级别的，我们的总状态数是 $n\log n$ 级别。

我们的状态数大概无法继续优化了，但我们的 $d p$ 转移是可继续优化的。
我们用 $c (l, r)$ 表示将区间 $[l, r]$ 划分一段所产生的贡献，则转移式为：
$dp_{i,k}=\min_{j=0}^{i-1}\left(dp_{j,k-1}+c(j+1,i)\right)$ 显然，这个 $d p$ 转移是单调的，对于 $k$ 相同的 $d p$ ，显然我 $i$ 越大，我们的划分点就会继续右移。
事实上，我们可以通过说明对于 $l < l^{'} < r^{'} < r$ ，有 $c(l,r)+c(l',r')\geqslant c(l,r')+c(l',r)$ 来证明它的单调性。
而这个式子显然是成立的，前面的部分比后面多了区间 $[l, l^{'})$ 与区间 $(r^{'}, r]$ 间的贡献。
这样的话，我们就可以用分治优化我们的 $d p$ 转移了。

但无论怎么转移，我们都需要快速求出我们的 $c (l, r)$ 呀。
推一推 $c$ 的式子。
$c(l,r)=\sum_{i=l}^{r}\sum_{j=i}^{r}[(i,j)\geqslant l]=\sum_{d=l}^{r}\sum_{i=l}^{r}\sum_{j=i}^{r}[(i,j)=d]\\ =\sum_{d=l}^{r}\sum_{i=1}^{\lfloor\frac{r}{d}\rfloor}\sum_{j=1}^{i}[(i,j)=1]=\sum_{d=l}^{r}\sum_{i=1}^{\lfloor\frac{r}{d}\rfloor}\varphi(i)=\sum_{d=l}^{r}s(\frac{r}{d})$ 其中 $s(n)=\sum_{i=1}^n\varphi(i)$ ，也就是 $\varphi$ 的前缀和。
而这就可以整除分块了，我们可以先预处理一下块的前缀和，每次查询就算一下它所在块后缀和，再加上整块的后缀和就行了。
这样就可以做到预处理 $O\left(n\sqrt n\right)$ ，单次查询 $O\left(1\right)$ 。
事实上我们可以再将整个 $d p$ 数组都预处理了，然后每次询问就可以 $O\left(1\right)$ 回答了。

总时间复杂度 $O\left(n\log^2 n+n\sqrt n\right)$ 。

源码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double Ld;
typedef pair<LL,LL> pii;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mo=998244353;
const int mod=1e6+7;
const int inv2=499122177;
const int inv3=332748118;
const int jzm=2333;
const int zero=2000;
const int n1=100;
const int lim=100000;
const int orG=3,ivG=332748118;
const double Pi=acos(-1.0);
const double feps=1e-11;
const double eps=1e-9;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0)putchar('-'),print(-x);if(x>9)print(x/10);putchar(x%10+'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int T,n,K,prime[MAXN],cntp,phi[MAXN];
LL pre[MAXN],dp[MAXN][20],mp1[MAXN][405],mp2[MAXN][405];
int al[MAXN],ar[MAXN],idx;
bool oula[MAXN];
void init(){
	pre[1]=1;
	for(int i=2;i<=n;i++){
		if(!oula[i])prime[++cntp]=i,phi[i]=i-1;
		for(int j=1;j<=cntp&&i*prime[j]<=n;j++){
			oula[i*prime[j]]=1;
			if(i%prime[j]==0){phi[i*prime[j]]=prime[j]*phi[i];continue;}
			else phi[i*prime[j]]=(prime[j]-1)*phi[i];
		}
		pre[i]=pre[i-1]+phi[i];
	}
	for(int i=1;i<=n;i++){
		idx=0;LL summ=0;
		for(int l=1,r;l<=i;l=r+1)
			r=i/(i/l),idx++,al[idx]=l,ar[idx]=r;
		for(int j=idx;j>0;j--){
			summ+=1ll*(ar[j]-al[j]+1)*pre[i/ar[j]];
			if(al[j]<=i/al[j])mp1[i][al[j]]=summ;
			else mp2[i][i/al[j]]=summ;
		}
	}
}
LL work(int L,int R){
	if(L>R)return 0;int r=R/(R/L)+1;
	return 1ll*(r-L)*pre[R/L]+(r<=R/r?mp1[R][r]:mp2[R][R/r]);
}
void sakura(int l,int r,int L,int R,int k){
	int mid=l+r>>1;dp[mid][k]=INF;
	LL tmp=work(R+1,mid);int mk=0;
	for(int i=min(mid,R);i>=L;i--){
		if(dp[i][k-1]+tmp<dp[mid][k])
			dp[mid][k]=dp[i][k-1]+tmp,mk=i;
		if(i&&i<=mid)tmp+=pre[mid/i];
	}
	if(l<mid)sakura(l,mid-1,L,mk,k);
	if(r>mid)sakura(mid+1,r,mk,R,k);
}
int main(){
	read(T);n=100000;K=16;init();
	dp[0][0]=0;for(int i=1;i<=n;i++)dp[i][0]=INF;
	for(int i=1;i<=K;i++)sakura(0,n,0,n,i);
	while(T--){
		read(n);read(K);
		if(K>16||(1<<K)-1>=n){printf("%d\n",n);continue;}
		printf("%lld\n",dp[n][K]);
	}
	return 0;
}