AcWing 1221. 四平方和
原题链接
简单
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5000010;
int n, s;
int C[N], D[N];
int main()
{
cin >> n;
memset(C, -1, sizeof C);
for (int c = 0; c * c <= n; c++)
{
//用哈希表将c^2 + d^2的值存入相应的c和d
for (int d = 0; d * d <= n; d++)
{
s = c * c + d * d;
if (C[s] == -1) //后面发现c^2+d^2的值相等只存第一次,即字典序最小的
C[s] = c, D[s] = d;
}
}
for (int a = 0; a * a <= n; a++)
{
for (int b = a;a * a + b * b <= n; b++) //加法满足交换律,a从零开始后,b就不用从零开始了
{
s = n - a * a - b * b;
if (C[s] != -1)
{
printf("%d %d %d %d\n", a, b, C[s], D[s]);
return 0;
}
}
}
return 0;
}