cpp.sb2's blog

By cpp.sb2, history, 4 years ago, In English

$$$a^{3}+b^{3}$$$ 是一个对称式(即交换 $$$a,b$$$ 原式值不变)。所以可以认为 $$$a<=b$$$,因为 $$$a>b$$$ 的情况相当于把 $$$a$$$ 与 $$$b$$$ 交换。

所以可以直接枚举 $$$a$$$,然后算出 $$$b=^{3}\kern{-8pt}\sqrt{n-a^{3}}$$$。如果 $$$b$$$ 是正整数,则输出yes并结束程序。否则继续枚举。若枚举完所有 $$$a$$$ 仍未找到,则输出no

现在的重点是如何求 $$$^{3}\kern{-8pt}\sqrt{n-a^{3}}$$$,设结果为 $$$ans$$$,由于 $$$ans^{2}$$$ 满足单调性,所以二分 $$$ans$$$ 即可。

小技巧:由于 $$$^{3}\kern{-8pt}\sqrt{n-a^{3}}$$$ 可能不为整数,这时如果把小数的值也枚举出来很费时间,所以只需要枚举其整数值,然后判断 $$$ans^{3}$$$ 是否等于 $$$n-a$$$ 即可。若等于则说明是整数,输出yes,否则继续枚举。

细节:注意二分的上界最多为 $$$10^{4}$$$ 。不然算立方时会爆longlong。

单组数据时间复杂度: $$$O(^{3}\kern{-8pt}\sqrt{x} \times log_{2}(x))$$$ 。

#include<iostream>
using namespace std;
long long sqrt3(long long a){
	long long l=1,r=min(10000ll,a),m;
	while(l<=r){
		m=l+r>>1ll;
		if(m*m*m<a){
			l=m+1ll;
		}else{
			r=m-1ll;
		}
	}
	return l;
}
void Main(){
	long long n,i,a,b=9223372036854775807ll; //b一定要初始化,否则一开始就进不去a<=b的循环。
	cin>>n;
	for(a=1;a<=b;a++){
		b=sqrt3(n-a*a*a);
		if(a*a*a+b*b*b==n){
			cout<<"yes"<<endl;
			return;
		}
	}
	cout<<"no"<<endl;
}
int main(){
	long long t,i;
	cin>>t;
	for(i=0;i<t;i++){
		Main();
	}
	return 0;
}
  • Vote: I like it
  • -140
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it -37 Vote: I do not like it

Hey,here is Codeforces,there are no any Chineses(?).And don't copy your solution in Luogu here.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    I think you should check your grammar mistakes. And excuse me for that, you're a Chinese yourself.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      So you mean Chinese cannot remind another Chinese not to speak Chinese in codeforces?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    No any Chinese??? Then where are Rank 7&10 from and where are you from???

»
4 years ago, # |
  Vote: I like it -40 Vote: I do not like it

您太强了!Orz

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Come on bro, Codeforces isn't a Chinese community.

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

You'd better use English in Codeforces. And don't copy your Luogu blog to here.

»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Codeforces is an international platform of cp,so please use English here.

If you really want to post this blog,put it somewhere else(maybe you own blog) instead of here.

»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Oh!You is an Chinese men!(big fog

»
4 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Even if the language problem is fixed,this blog is still a meaningless one.
Hardly people else would like to read this blog only to read such an easy problem's solution.
Besides,the official solution is clear enough,and you didn't use a new method.
So delete it yourself,please.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why... It's easy for you maybe, but not for everyone. If the language problem is fixed, it's useful to come up with a new solution or explain the solution in a different way.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      But this blog is almost the same as the official solution...
      I think there is no need to read.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Emmmmmmmmmmm He gave us his implementation,however. It must be useful in some way.

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

So why are you an Englishman???

»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

This kind of problems are too easy and it's useless for cf user.I think you can make the whole unofficial editorial(≥5 problems) or you'd better make it in your own blog not codeforces.