AcWing 1221. 四平方和
原题链接
简单
作者:
CqAq
,
2024-03-26 23:35:34
,
所有人可见
,
阅读 1
算法1
本地都能过,这里就是MLE
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5E7 +11;
ll n, hash1[N], hash2[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
memset(hash1, -1, sizeof hash1);
//memset(hash2, -1, sizeof hash2);
for(int c = 0; c * c <= n; ++ c)
for(int d = c; d * d + c * c <= n; ++ d){
int s = c * c + d * d;
if(hash1[s] == -1)
hash1[s] = c, hash2[s] = d;
}
for(int a = 0; a * a <= n; ++ a)
for(int b = a; b * b + a * a <= n; ++ b){
int s = n - a * a - b * b;
if(hash1[s] != -1){
cout << a << ' ' << b << ' ' << hash1[s] << ' ' << hash2[s];
return 0;
}
}
return 0;
}