AcWing 1221. 四平方和
原题链接
简单
作者:
lyf11
,
2021-02-20 20:11:53
,
所有人可见
,
阅读 375
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5 * 1e6;
struct Sum {
int s, c, d;
bool operator< (const Sum &t) const {
if (s != t.s) return s < t.s;
if (c != t.c) return c < t.c;
return d < t.d;
}
}S[N];
int n, m;
int main() {
cin >> n;
for (int a = 0; a * a <= n; ++a) {
for (int b = a; a * a + b * b <= n; ++b)
S[m++] = {a * a + b * b, a, b};
}
sort(S, S + m);
for (int a = 0; a * a <= n; ++a) {
for (int b = a; a * a + b * b <= n; ++b) {
int t = n - a * a - b * b;
int l = 0, r = m - 1;
while (l < r) {
int mid = l + r >> 1;
if (S[mid].s >= t) r = mid;
else l = mid + 1;
}
if (S[l].s == t) {
cout << a << " " << b << " " << S[l].c << " " << S[l].d << endl;
return 0;
}
}
}
return 0;
}