526互联

Atcoder Grand Contest 057 D - Sum Avoidance

发布时间 2023-07-20 08:56:52作者: tzc_wk

先来找些性质：

  • \(A\) 中最小的元素 \(M\) 肯定是最小的不是 \(S\) 的因子的数，由于 \(\text{lcm}(1,2,3,\cdots,43)>10^{18}\)，所以 \(M\le 43\)。
  • 对于每个 \(0\le i<M\)，\(\bmod M=i\) 的数被选择的部分必然是一段后缀，因为如果你选择了 \(M\) 选择了某个 \(\bmod M=i\) 的数 \(v\)，那么再选 \(v+M\) 也是不会有影响的。
  • 考虑扩展得到最优解对应的 \(A\) 的过程，必然是我从 \(A=\{M,2M,3M,\cdots,\lfloor\dfrac{S-1}{M}\rfloor·M\}\) 开始，每次找到最小的满足”加入这个数以后得不到 \(S\)“的数 \(v\)，将 \(v,v+M,v+2M,\cdots\) 加入 \(A\)。

现在考虑如何求解答案。由于我们暴力扩展最多只会扩展 \(M-1\) 轮，所以我们可以暴力求出每次要加入的数 \(\bmod M\) 的值，这一脸同余最短路的样子，具体来说我们实时维护个 \(mn_i\) 表示 \(\bmod M=i\) 的数当中最小的能够表示为 \(A\) 中数的线性组合的数，这样我们可以在 \(O(M)\) 的时间内算出 \(\bmod M=i\) 的数当中最小的满足加入这个数之后 \(S\) 不能被表示出来的数。这样我们求出了每个 \(\bmod M\) 的等价类最小的在 \(A\) 中的数，直接二分求第 \(k\) 小即可。

时间复杂度 \(O(TM^3)\)。

const ll INF=0x3f3f3f3f3f3f3f3fll;
ll S,K,mn[45],val[45];int m;
ll calc(ll p){
	ll sum=0;
	for(int i=0;i<m;i++)if(val[i]<=p)sum+=(p-val[i])/m+1;
	return sum;
}
void solve(){
	scanf("%lld%lld",&S,&K);for(int i=2;;i++)if(S%i){m=i;break;}
	memset(mn,63,sizeof(mn));memset(val,63,sizeof(val));mn[0]=0;val[0]=m;
	while(1){
		int rem=0;ll mnv=INF;
		for(int i=1;i<=m-1;i++){
			if(val[i]!=INF)continue;ll mx=i;
			for(int j=1;j<=m-1;j++){
				int nd_rem=(S-j*i%m+m)%m;
				if(mn[nd_rem]!=INF)chkmax(mx,(S-mn[nd_rem]+j)/j);
			}
			while(mx%m!=i)++mx;
			if(mx<mnv)mnv=mx,rem=i;
		}if(mnv==INF)break;val[rem]=mnv;
		for(int i=1;i<=m-1;i++){
			if(1ll*i*mnv>S)break;
			for(int j=1;j<=m-1;j++){
				int nd_rem=(j-(mnv%m)*i%m+m)%m;
				chkmin(mn[j],mn[nd_rem]+i*mnv);
			}
		}
	}
	if(calc(S-1)<K)return puts("-1"),void();
	else{
		ll L=1,R=S-1,P=0;
		while(L<=R){
			ll mid=L+R>>1;
			if(calc(mid)>=K)P=mid,R=mid-1;
			else L=mid+1;
		}printf("%lld\n",P);
	}
}
int main(){
	int qu;scanf("%d",&qu);while(qu--)solve();
	return 0;
}