4 제곱 합 - 사유 - unoderedmap
모든 정 수 는 최대 4 개의 정수 의 제곱 합 을 나 타 낼 수 있다.
0 을 포함 하면 4 개의 제곱 합 을 나 타 낼 수 있다.
예 를 들 면:
5=02+02+12+22
7=12+12+12+22
주어진 정수 에 대해 서 는 여러 가지 제곱 과 표현법 이 존재 할 수 있다.
네 개의 수 를 정렬 하 라 고 요구 합 니 다:
0≤a≤b≤c≤d
그리고 모든 가능 한 표현법 에 대해 a, b, c, d
연합 메 인 키 의 오름차 순 을 배열 하기 위해 마지막 으로 첫 번 째 표현 법 을 출력 합 니 다.입력 형식 은 정수 N 출력 형식 을 입력 하여 4 개의 비 마이너스 정 수 를 출력 하고 작은 것 부터 큰 것 까지 정렬 하 며 중간 에 빈 칸 으로 나 눕 니 다.데이터 범위 0 입력 샘플: 5 출력 샘플: 0 01 2
방법: 1. 정상 적 인 폭력 으로 하 는 것 은 n3 의 복잡 도가 뚜렷 하고 폭력 이 안 됩 니 다. 지금 은 공간 으로 시간 을 바 꾸 고 n2 의 방법 으로 해 야 합 니 다.2. unordered 이용map 는 먼저 옮 겨 다 니 는 c 와 d 의 정 보 를 저장 하고 a, b 의 옮 겨 다 니 며 2 회 for 로 해결 할 수 있 습 니 다. 그 중에서 unorderedmap 의 find 복잡 도 는 o (1)
#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;
int n;
unordered_map <int, int> f;
int main(){
cin >> n;
for(int c = 0; c * c <= n / 2; c++){
for(int d = c; c * c + d * d <= n; d++){
if(f.find(c * c + d * d) == f.end()){
f[c*c + d * d] = c;
}
}
}
for(int a = 0; a * a * 4 <= n; a++){
for(int b = a; b * b + a * a <= n / 2; b++){
if(f.find(n - a * a - b * b) != f.end()){
int c = f[n - a * a - b * b];
int d = int(sqrt(n - a * a - b * b - c * c) * 1.0);
cout << a << " " << b << " " << c << " " << d << endl;
return 0;
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
