网站建设经济效益,情感营销,免备案网站建设,网页入口网站推广题目描述
四方定理是数论中著名的一个定理#xff0c;指任意一个自然数都可以拆成四个自然数的平方之和。例如#xff1a;
251^22^22^24^2
对 25来说#xff0c;还有其他方案#xff1a;
250^20^23^24^2
以及
250^20^20^25^2
给定一个自然数 n #xff0c;请输出 n…题目描述
四方定理是数论中著名的一个定理指任意一个自然数都可以拆成四个自然数的平方之和。例如
251^22^22^24^2
对 25来说还有其他方案
250^20^23^24^2
以及
250^20^20^25^2
给定一个自然数 n 请输出 n 的所有四平方拆分方案。
输入格式
单个整数表示 n。
输出格式
若干行每行四个由小到大排列的自然数表示一种拆分方案。如果有多种方案先输出首项较小的方案对于首项相同的方案先输出第二项较小的方案其他情况以此类推。
数据范围
0≤n≤1,000,000
输入样例
25输出样例
0 0 0 5
0 0 3 4
1 2 2 4
思路解析
用多重循环后sort。
AC代码
#includebits/stdc.h
using namespace std;
int main() {int n;cinn;vectorvectorint s;for(int i0;i*in;i) {for(int ji;j*jn-j*j;j) {for(int kj;k*kn-i*i-j*j;k) {int l_sqrtn-i*i-j*j-k*k;int lstatic_castint(sqrt(l_sqrt));if(l_sqrtl*llk) {s.push_back({i,j,k,l});}}}}sort(s.begin(),s.end());s.erase(unique(s.begin(),s.end()),s.end());for(const vectorint sol : s) {for(int val : sol) {coutval ;}cout\n;}return 0;
}
