[Codeforces][Round #702][Div.3] C : Sum of Cubes (C++)

https://codeforces.com/contest/1490/problem/C

Problem - C - Codeforces

 

 

[난이도] Div.3
[유형] 이분탐색

[풀이]
x<=10^12로 x가 큰 숫자여도 a^3+b^3=x 이므로 a,b는 아무리 커도 10^4보다 작은 수이다.
1~10^4 범위의 a를 모두 검사하면서 이분탐색으로 a^3+b^3=x를 만족하는 b를 1~10^4 범위에서 찾으면 된다.

 

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
int tc;
ll x;
 
bool solve(){
 
    ll a = min(10000LL,(ll)sqrt(x));
 
    for(ll i=1;i<=a;i++){
 
 
        ll lo=0,hi=a+1;
        while(lo+1<hi){
 
            ll mid = (lo+hi)/2;
            
            ll v = i*i*i+mid*mid*mid;
            if(v==x) return true;
            if(v>x) hi = mid;
            else lo = mid;
 
        }
        //printf("i:%d, lo:%lld\n",i,lo);
    }
    return false;
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%lld",&x);
 
        if(solve()) puts("YES");
        else puts("NO");
    }
 
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round702-Div.3/C.cpp