文件详细信息

下载本文件

本文件的大小为 944 字节。

#include<cstdio>
typedef __int128 ll;
const ll one=1;
template<typename T>
void write(T a){
	static int ch[50],cnt;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	cnt=0;
	while(a)ch[++cnt]=a%10|48,a/=10;
	while(cnt)putchar(ch[cnt--]);
}
int k,m;
ll pw2[120],f[120];
ll calc(ll n){
	ll sum=0;
	int delta=0;
	for(int i=k;i>=0;i--)
		if(pw2[i]&n)
			sum+=f[i]+(delta++)*pw2[i];
	return sum;
}
bool check(ll lim){
	ll pos=0;
	int cnt=0;
	while(pos<pw2[k]-1){
		ll l=pos,r=pw2[k]-1,mid,ans=pos;
		while(l<=r){
			mid=(l+r)>>1;
			if(calc(mid)-calc(pos)<=lim)l=mid+1,ans=mid;
			else r=mid-1;
		}
		cnt++;
		pos=ans;
		if(cnt>m)return false;
	}
	return true;
}
int main(){
	scanf("%d%d",&k,&m);
	pw2[0]=1;
	for(int i=1;i<=k;i++)pw2[i]=pw2[i-1]<<1;
	f[0]=1;
	for(int i=1;i<=k;i++)f[i]=(f[i-1]<<1)+pw2[i-1]-1;
	ll l=1,r=f[k],m,ans=f[k];
	while(l<=r){
		m=(l+r)>>1;
		if(check(m))r=m-1,ans=m;
		else l=m+1;
	}
	write(ans),putchar('\n');
	return 0;
}