C. Sum of Cubes-蒲公英云

C. Sum of Cubes

传送门
在这里插入图片描述
题目大意：
a 3 + b 3 = x a^3+b^3=x a3+b3=x,是否存在这样的 a a a和 b b b

题解：
(1）数据范围: 1 0 12 10^{12} 1012
(2) 想过用数组 a [ i ] = i ∗ i ∗ i ; b [ a [ i ] ] = t r u e ; a[i] = i * i * i;b[a[i]] = true; a[i]=i∗i∗i;b[a[i]]=true;来解决，但是数组的长度有限定，
size if array is not bigger than 1e9
(3)先暴力让 i i i 从1到 1 0 12 / 3 10^{12/3} 1012/3把存在数组中，b = n - a[i];用二分搜索在a[i]里面找到b。
(4）时间复杂度：n * logn

#include <iostream>
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const ll maxn = 1e4;
ll a[maxn+5];
//ll b[maxn]; size if array is not bigger than 1e9
bool binary_search(ll key, ll a[], ll n)
{ 
    ll low = 1;
    ll high = n;
    ll mid;
    while (low <= high)
    { 
        mid = (low + high) / 2;
        if(key < a[mid])
            high = mid - 1;
        else if(key > a[mid])
            low = mid + 1;
        else if(key == a[mid])
            return true;
    }
    return false;
}
int main(){ 
    ios;
    for (ll i = 1; i <= maxn; i++)
        a[i] = i * i * i;
    int t;
    cin >> t;
    while( t-- ){ 
        ll n;
        cin >> n;
        bool flag = false;
        for (ll i = 1; i <= maxn; i++) { 
            ll temp = n - a[i];
            if(!temp)
            { 
                cout << "NO" <<  endl;
                flag = true;
                break;
            }
            else if(binary_search(temp, a, maxn)) 
            { 
                cout << "YES" << endl;
                flag = true;
                break;
            }
        }
        if (!flag) cout << "NO" << endl;
    }
    return 0;
}