C. Sum of Cubes

布满荆棘的人生 2022-11-08 11:27 136阅读 0赞

[传送门][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]  
题目大意：  
 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;
    }

[Link 1]: https://codeforces.ml/contest/1490/problem/C
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221023/349fff42392345b2a6f4881d34d41a5d.png