ACM-基础-二分查找 HDU6288 2018字节跳动杯C题

题目链接

二分查找答案
我当时真的第一次见这种题型。
代码
1.1e18 unsigned long long 肯定可以装下K
2.【n】^a*【log2(n)】^b肯定爆unsigned long long(k) 所以只能除法解决
3.注意取对数时,分母可能是0(不能整除0)
4.直接ans存储答案，不要费心力去判断取L还是取R

#include<bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
int a,b;
ull k,ans;
bool check(ull mid,ull k){//
    for(int i=0;i<a;i++){
        if(k<mid)return false;//too big
        k/=mid;
    }
    ull x=(ull)ceil(log2(mid));//loge(mid);(RE(div 0)
    if(x==0)return true;
    for(int i=0;i<b;i++){
        if(k<x)return false;
        k/=x;
    }
    return true;
}
int main(){
    int t;
    //freopen("1.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>t;
    ull l,r,n,x,mid;
    while(t--){
        cin>>a>>b>>k;
        l=0,r=k;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid,k)){
                //cout<<"mid="<<mid<<endl;
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41