缺失的数据范围 2018中国大学生程序设计竞赛-女生专场_ccpc2018-hangzhou-problemset 测试数据

不难发现随着 n 的增大，na (⌈log2 n⌉)b 的值不会减小，反之亦然。二分查找最大的满足 na (⌈log2 n⌉)b 不超过 k 的 n 即可。 有两点需要注意：

• 乘法可能溢出 64 位整数，需要特殊处理。 

• 求 ⌈log2 n⌉ 时不应使用实数计算，这将带来误差，应当使用整数计算。 时间复杂度 O(log2 k)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define  Max int(1e9+1) 
int t,a,b;
ll k; 
inline ll mul(ll a,ll b){
  if(!a||!b)return 0;
  if(a>(k+5)/b)return k+5;
  a*=b;
  return a>k+5?k+5:a;
}
inline ll getpow(ll a,int b){
  ll t=1;
  while(b--)t=mul(t,a);
  return t;
}
inline int getlog(ll n){
  ll o=n;
  while(o%2==0)o/=2;
  int t=0;
  while(n>1)n/=2,t++;
  if(o>1)t++;
  return t;
}
ll computer(ll n)
{
    return mul(getpow(n,a),getpow(getlog(n),b));
}
int main()  
{  
	scanf("%d",&t);
    while(t--)
    {
		scanf("%d%d%lld",&a,&b,&k);
    	ll le=2,ri=k,mid,ans=1;
    	while(le<=ri)
    	{
    		mid=(le+ri)/2;
    		if(computer(mid)<=k)
    		   {
    		   	ans=mid;
    		   	le=mid+1;
			   }
			else
			   ri=mid-1;   
		}
		printf("%lld\n",ans);
	}
} 
 

比赛的时候看着大佬们都AC了，心里万分焦急，想想自己16、17女生赛的题都没有补就去比赛，想想自己也是可笑，不知道哪里的勇气觉得自己可以AC。恩，以后要开始注重补题这一环节了