四平方和题目链接

问题描述

【题目描述】
【输入】

【输出】

【样例输入】

5
12
773535

【样例输出】

0 0 1 2
0 2 2 2
1 1 267 838

题目解析

枚举$a,b,c,d$四个数字，同时也要注意优化，这里采用的是四层循环减为双层循环，先枚举$c,d$两个较大的变量，在$cache[c\ast c+d\ast d]$中存入较小数$c$，当再枚举$a,b$两个较小的变量时，只需要查找$cache[N-a\ast a-b\ast b]$是否存在即可，如果存在说明已经找到了$a\ast a+b\ast b+c\ast c+d\ast d=N$等式的解。

C++代码

#include<bits/stdc++.h>
using namespace std;
int N;
map<int,int> cache;
int main()
{scanf("%d",&N);for(int c=0;c*c<=N/2;c++)for(int d=c;c*c+d*d<=N;d++)if(cache.find(c*c+d*d)==cache.end())cache[c*c+d*d] = c;for(int a=0;a*a<=N/4;a++){for(int b=a;a*a+b*b<=N/2;b++){if(cache.find(N-a*a-b*b)!=cache.end()){int c = cache[N-a*a-b*b];int d = int(sqrt(N-a*a-b*b-c*c));printf("%d %d %d %d\n",a,b,c,d);return 0;}}}return 0;
}