缺失的数据范围
著名出题人小Q出过非常多的题目，在这个漫长的过程中他发现，确定题目的数据范围是非常痛苦的一件事。
每当思考完一道题目的时间效率，小Q就需要结合时限以及评测机配置来设置合理的数据范围。 因为确定数据范围是一件痛苦的事，小Q出了非常多的题目之后，都没有它们设置数据范围。对于一道题目，小Q会告诉你他的算法的时间复杂度为O(nalogbn)O(nalogbn)，且蕴含在这个大OO记号下的常数为11。同时，小Q还会告诉你评测机在规定时限内可以执行kk条指令。小Q认为只要na(⌈log2n⌉)bna(⌈log2n⌉)b不超过kk，那么就是合理的数据范围。其中，⌈x⌉⌈x⌉
表示最小的不小于xx的正整数，即xx上取整。
自然，小Q希望题目的数据范围nn越大越好，他希望你写一个程序帮助他设置最大的数据范围。 Input第一行包含一个正整数T(1≤T≤1000)T(1≤T≤1000)，表示测试数据的组数。
每组数据包含一行三个正整数a,b,k(1≤a,b≤10,106≤k≤1018)a,b,k(1≤a,b≤10,106≤k≤1018)，分别描述时间复杂度以及允许的指令数。Output对于每组数据，输出一行一个正整数nn，即最大可能的nn。
Sample Input3
1 1 100000000
2 1 100000000
1 3 200000000
Sample Output
4347826
2886
48828
嗯。。数学题。。不会。。
二分，等式两边同时取对数，注意精度。
AC代码（抄的别的博客）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m,i,a,b,k,ans;
ll fast(ll x,ll y)
{
ll num=1;
while(y)
{
if(y%2!=0)
num*=x;
x*=x;
y/=2;
}
return num;
}
ll logn2(ll m)
{
ll i;
for(i=1;i<=64;i++)///枚举2的幂~
{
if(fast(2,i)>=m)
return i;
}
}
int judge(ll mid)
{
ll i,m;
ll num1=1,num2=1;
for(i=0;i<a;i++)
{
if(num1<k/mid)///n的a次幂
num1*=mid;
else
return 0;///大于给定值
}
m=logn2(mid);///取整，这里卡ceil()!!!还是自己写叭
if(m==0)
return 1;///确保下面分母不为零，n=1时
else
{
num2=1;
for(i=0;i<b;i++)
{
if(num2<=k/m)
num2*=m;///log2(n)向上取整的b次幂
else
return 0;///大于给定值，跳出
}
}
if(num1<=k/num2)///小于给定值，是为了防爆吗??
return 1;
else
return 0;
}
int main()
{
ll l,r,mid;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&k);
l=0;
r=1e18+1;
while(l<=r)
{
mid=(l+r)/2;
if(judge(mid)==1)
l=mid+1;
else
r=mid-1;
}
cout<<r<<'\n';
}
return 0;
}
不知道为啥把快速幂换成1<<i就re了。为啥？？（期待大佬解答！）
还不知道这样做为啥取对数时不会有损失。（期待大佬解答！）
京公网安备 11010502036488号