提供一种思路:二分答案

一.题意:

略

二.正确性:

1.答案具有单调性

假设最初选了 $a$ 道题时将会完成 $b$ 道题,当我们最初选 $c>a$ 道题时,将会完成 $d>b$ 道题,反之亦然.

所以我们可以得出结论:最初选的题越多,最终完成的题越多,答案具有单调性满足二分条件.

三.做法:

我们以 $1$ 为左边界, $k$ 为右边界对最初选择题目数量进行二分,对每次二分暴力检查最终完成题数是否 $>=k$ .同时特判$p$ 或 $k=0$ 的情况和 $p$ 或 $k=1$ 的情况.

当 $p$ 或 $k=0$ 时,最初选择题目数量显然为 $0$.

当 $p$ 或 $k=1$ 时,最初选择题目数量显然为 $1$.

暴力检查思路为:模拟题目操作.

详见代码

四.时间复杂度:

一共有t组数据,对每组数据进行二分的时间复杂度为 $log(k)$ ,每次二分暴力检查的时间复杂度约为 $log_p(k)$ ,证明如下:

根据题意,设未进行过加题处理的题目数量为x,每次操作会将 $x$ 变为 $x/p+x$ ,当无法操作时操作数约为 $log_p(x)$.

五:代码:

#include<bits/stdc++.h>
using namespace std;
int t;
int p,k;
int l,r;
int mid;
int res,ans;

bool check(int x){//暴力检查 
  res=x%p+x/p;
  x=x/p*p;
	while(res/p){
		x+=res/p*p;
		res=res%p+res/p;
	}
	x+=res;
	
	if(x>=k)
	  return true;
	else
	  return false;  
}

int Main(){
	cin>>t;
	
	while(t--){
		cin>>p>>k;
		l=0,r=k+1;
		if(!p||!k){//特判p=0或k=0 
			cout<<0<<'\n';
			continue;
		}
		else if(p==1||k==1){//特判p=1或k=1 
			cout<<1<<'\n';
			continue;
		}
		else{
				while(l<r){//二分查找最初题目数量 
				mid=(l+r)>>1;
				if(check(mid))
					r=mid;
				else
				  l=mid+1;	
			}
		
			for(int i=max(1,mid-20);i<=min(mid+20,k);i++)//二分防挂,不影响整体时间复杂度 
			  if(check(i)){
			  	cout<<i<<'\n';
			  	break;
				}	
		}	
		
	}
		
	return 0;
}