温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何用整数二分实现四平方和

发布时间:2021-10-09 16:09:15 来源:亿速云 阅读:141 作者:iii 栏目:编程语言

这篇文章主要介绍“如何用整数二分实现四平方和”,在日常操作中,相信很多人在如何用整数二分实现四平方和问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”如何用整数二分实现四平方和”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

#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;
}

到此,关于“如何用整数二分实现四平方和”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI