1 Star 2 Fork 0

YangZhi1605 / CSDNCode

Create your Gitee Account
Explore and code with more than 12 million developers,Free private repositories !:)
Sign up
This repository doesn't specify license. Please pay attention to the specific project description and its upstream code dependency when using it.
Clone or Download
四的平方和——数组模拟哈希法.cpp 857 Bytes
Copy Edit Raw Blame History
YangZhi1605 authored 2022-02-21 21:51 . csdn二分
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5000010;
int h[N][3];
int n;
int main(int argc, char** argv) {
cin >> n;
for(int c = 0; c*c <= n; c++)
for(int d = c; d*d + c*c <= n; d++){
int tmp = d*d + c*c;
//哈希表中,当前位置没有数据才记录,倘若冲突了,也可以保证优先记录字典序较小的
if(h[tmp][0] == 0) {
h[tmp][0] = tmp;
h[tmp][1] = c;
h[tmp][2] = d;
}
}
for(int a = 0; a*a <= n; a++)
for(int b = a; b*b + a*a <= n; b++) {
int ans = n - a*a-b*b;
if(h[ans][0] != 0){
cout << a << " " << b << " " << h[ans][1] << " " << h[ans][2];
return 0;
}
}
return 0;
}
C++
1
https://gitee.com/twopointers/csdncode.git
git@gitee.com:twopointers/csdncode.git
twopointers
csdncode
CSDNCode
master

Search

53164aa7 5694891 3bd8fe86 5694891