如何用整數二分實現四平方和

這篇文章主要介紹“如何用整數二分實現四平方和”，在日常操作中，相信很多人在如何用整數二分實現四平方和問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何用整數二分實現四平方和”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;
const int N =2500010;

//結構體
struct Sum{
    int s,c,d;
    //重載運算符
    bool operator< (const Sum &t)const{
        if(s!=t.s) return s<t.s;
        if(c!=t.c) return c<t.c;
        return d<t.d;
    }
}sum[N];

int n,m;

int main(){
    cin>>n;
    //枚舉c、d并存下來
    for(int c=0;c*c<=n;c++){
        for(int d=c;c*c+d*d<=n;d++){
            sum[m++]={c*c+d*d,c,d};
        }
    }
    //排序
    sort(sum,sum+m);
    //枚舉a、b
    for(int a=0;a*a<=n;a++){
        for(int b=0;a*a+b*b<=n;b++){
            int t=n-a*a-b*b;
            //區間
            int l=0,r=m-1;
            //性質
            while(l<r){
                int mid=(l+r)>>1;
                if(sum[mid].s>=t) r=mid;
                else l=mid+1;
            }
            if(sum[l].s==t){
                printf("%d %d %d %d",a,b,sum[l].c,sum[l].d);
                return 0;
            }
        }
    }
    return 0;
}

到此，關于“如何用整數二分實現四平方和”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！