[蓝桥杯 2016 省 AB] 四平方和

题目描述

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多?4个正整数的平方和。

如果把?0?包括进去，就正好可以表示为?4?个数的平方和。

比如：

5=0^2+0^2+1^2+2^2。

7=1^2+1^2+1^2+2^2。

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对?44?个数排序使得0≤a≤b≤c≤d。

并对所有的可能表示法按 a,b,c,d?为联合主键升序排列，最后输出第一个表示法。

输入格式

程序输入为一个正整数 N(N<5×106)。

输出格式

要求输出?44?个非负整数，按从小到大排序，中间用空格分开。

输入输出样例

输入 #1复制

5

输出 #1复制

0 0 1 2

输入 #2复制

12

输出 #2复制

0 2 2 2

输入 #3复制

773535

输出 #3复制

1 1 267 838

说明/提示

时限 3 秒, 256M。蓝桥杯 2016 年第七届省赛

蓝桥杯 2016 年省赛 A 组 H 题（B 组 H 题）。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int n;
  cin>>n;
  for(int i=0; i<=sqrt(n); i++)
  {
    for(int j=i; i*i+j*j<=n; j++)
    {
      for(int k=j; i*i+j*j+k*k<=n; k++)
      {
        int h=n-i*i-j*j-k*k;
        int o=sqrt(h);
        if(o*o==h)
        {
          cout<<i<<" "<<j<<" "<<k<<" "<<o;
          return 0;
        }
      }
    }
  }
}