题解 CF1490C 【Sum of Cubes】

珂能并不会有更好的阅读体验

Description

题目 Link

• 给一个数 $x$ ，判断其是否能表示为两个立方数之和。
• 即：是否存在 $a,b$ 使 $a^3+b^3=x$。
• $t$ 组询问，$1\le t\le 100,1\le x\le 10^{12}$。

暴力即可......

只需要在 $[1,\sqrt[3]{x}]$ 范围内暴力查找 $a$，然后计算 $x-a$ 是否为完全立方数即可。

计算 $x-a$ 是否为完全立方数时，可以提前用 map 把 $[1,10^{12}]$ 内的所有完全立方数存一遍，也可以用 pow 来开三次根号判断qwq。

顺便，不要乱想那个什么 $a^3+b^3=(a+b)(a^2-ab+b^2)$，然后枚举 $x$ 的所有因数qwq，这么做复杂度很屑的/dk

我是开了个 map，不过这样会多一个 $\log$，导致复杂度变为 $O(t\sqrt[3]{x}\log10000)$。

不开 map 的话复杂度就是直接 $O(t\sqrt[3]{x})$ 的qwq。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>

#define int long long

using namespace std;

int t,x;

map<int,int>mp;

signed main(){

    mp.clear();
    for(int i=1;i<=10000;i++)mp[i*i*i]=1;

    cin>>t;
    while(t--){
        cin>>x;
        int f=0;
        for(int i=1;i*i*i<=x;i++){
            int t=i*i*i;
            if(mp[x-t]==1){
                cout<<"YES\n";
                f=1;
                break;
            }
        }
        if(!f)cout<<"NO\n";
    }

    return 0;
}