[已解决]检测一个数是否为两数平方和 c++ timeout

Yakia

检查一个数是否为两数平方之和 总是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;
}

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-22 15:20:51

提供几个优化思路：
1、循环时i的值只需要到sqrt(n),不需要到n
2、考虑到奇数的平方只可能是4n+1的形式，偶数的平方只可能是4n的形式。
     那么一个数：
                     如果除以4余0，那么它只可能是两个偶数的平方和
                     如果除以4余1，那么它只可能是一个奇数一个偶数的平方和
                     如果除以4余2，那么它只可能是两个偶数的平方和
                     如果除以4余3，那么它不可能是两个数的平法和

跳转到最佳答案楼层

Croper

提供几个优化思路：
1、循环时i的值只需要到sqrt(n),不需要到n
2、考虑到奇数的平方只可能是4n+1的形式，偶数的平方只可能是4n的形式。
     那么一个数：
                     如果除以4余0，那么它只可能是两个偶数的平方和
                     如果除以4余1，那么它只可能是一个奇数一个偶数的平方和
                     如果除以4余2，那么它只可能是两个偶数的平方和
                     如果除以4余3，那么它不可能是两个数的平法和