AcWing 1221. 四平方和
原题链接
简单
作者:
看不见
,
2023-03-28 13:48:57
,
所有人可见
,
阅读 160
vector数组
(省空间多时间)
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e6 + 10;
bool s[N];
vector<PII> v;
void check(int t) {
for (int i = 0; i < v.size(); i++) {
if (v[i].first * v[i].first + v[i].second * v[i].second == t) {
cout << v[i].first << ' ' << v[i].second << endl;
return;
}
}
}
int main()
{
int n;
cin >> n;
for (int c = 0; c * c <= n; c++)
{
for (int d = c; d * d + c * c <= n; d++)
{
v.push_back({ c,d });
s[d * d + c * c] = true;
}
}
for (int a = 0; a * a <= n; a++)
{
for (int b = 0; b * b + a * a <= n; b++)
{
if (s[n - a * a - b * b]) {
cout << a << ' ' << b << ' ';
check(n - a * a - b * b);
return 0;
}
}
}
}
哈希表
(空间换时间)
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N=5e6+10;
int C[N],D[N],n;
int main()
{
cin>>n;
memset(C,-1,sizeof C);
for(int c=0; c * c <= n; c++){
for(int d=c;d*d+c*c<=n;d++){
int sum=c*c+d*d;
if(C[sum] == -1){
C[sum]=c;
D[sum]=d;
}
}
}
for(int a=0; a * a <= n; a++){
for(int b=a;a*a+b*b<=n;b++){
int sum=n-a*a-b*b;
if(C[sum] != -1){
printf("%d %d %d %d\n",a,b,C[sum],D[sum]);
return 0;
}
}
}
}