四方定理c++题解

题目描述

四方定理是数论中著名的一个定理，指任意一个自然数都可以拆成四个自然数的平方之和。例如：

25=1^2+2^2+2^2+4^2

对 25来说，还有其他方案：

25=0^2+0^2+3^2+4^2

以及

25=0^2+0^2+0^2+5^2

给定一个自然数 n ，请输出 n 的所有四平方拆分方案。

输入格式

单个整数：表示 n。

输出格式

若干行：每行四个由小到大排列的自然数，表示一种拆分方案。如果有多种方案，先输出首项较小的方案，对于首项相同的方案，先输出第二项较小的方案，其他情况以此类推。

数据范围

0≤n≤1,000,000

输入样例

25

输出样例

0 0 0 5
0 0 3 4
1 2 2 4

思路解析

用多重循环后sort。

AC代码 

#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin>>n;vector<vector<int>> s;for(int i=0;i*i<=n;i++) {for(int j=i;j*j<=n-j*j;j++) {for(int k=j;k*k<=n-i*i-j*j;k++) {int l_sqrt=n-i*i-j*j-k*k;int l=static_cast<int>(sqrt(l_sqrt));if(l_sqrt==l*l&&l>=k) {s.push_back({i,j,k,l});}}}}sort(s.begin(),s.end());s.erase(unique(s.begin(),s.end()),s.end());for(const vector<int>& sol : s) {for(int val : sol) {cout<<val<<" ";}cout<<"\n";}return 0;
}