检测一个数是否为两数平方和 c++ timeout
检查一个数是否为两数平方之和 总是timeout 有什么更节省时间的写法吗？谢谢谢谢！(这里0是两数平方和)//return 最大的整数d，满足d*d<=n
unsigned int integer_sqrt(unsigned int x){
unsigned int d = sqrt(x);
while((d+1)*(d+1) <= x){
++d;}
while (d*d > x){
--d;}
return d;}
int main(){
int n;
cin >> n;
int is_sum=0;
int i=0;
int j=0;
bool found=false;
if(n==0){
is_sum=1;
}
else{
while(i<=n && !found){
j=sqrt(n-i*i);
if(i*i+j*j=n && j!=0){
is_sum=1;
found=true;
}
}
if (is_sum==1){cout << "sum of squares" <<endl;}
else{cout <<"not sum of squares" <<endl;}
return 0;
}
提供几个优化思路：
1、循环时i的值只需要到sqrt(n),不需要到n
2、考虑到奇数的平方只可能是4n+1的形式，偶数的平方只可能是4n的形式。
那么一个数：
如果除以4余0，那么它只可能是两个偶数的平方和
如果除以4余1，那么它只可能是一个奇数一个偶数的平方和
如果除以4余2，那么它只可能是两个偶数的平方和
如果除以4余3，那么它不可能是两个数的平法和
页:
[1]