C++로 구현하는 a² + b² = N을 만족하는 순서쌍 (a, b) 개수 찾기

하나의 자연수 N이 주어졌을 때, 두 양의 정수의 제곱합이 N이 되는 순서쌍(ordered pair)의 개수를 구하는 것이 이 글의 목표입니다.

다시 말해, 방정식 a² + b² = N을 만족하는 모든 (a, b) 조합을 찾는 문제입니다. 여기서 a는 √N 이하의 값만 살펴보면 충분하고, 각 a에 대해 b는 √(N − a²)로 계산할 수 있습니다.

예시를 통해 자세히 이해해 보겠습니다.

입력

N = 100

출력

a^2+b^2=N을 만족하는 쌍 (a, b)의 개수: 2

설명

가능한 쌍은 (6, 8)과 (8, 6)입니다. 6^2 + 8^2 = 36 + 64 = 100

입력

N = 11

출력

a^2+b^2=N을 만족하는 쌍 (a, b)의 개수: 0

설명

조건을 만족하는 쌍이 존재하지 않습니다.

알고리즘 접근 방법

• 정수 N을 입력받습니다.

• squareSum(int n) 함수는 n을 인자로 받아 제곱합이 n이 되는 순서쌍의 개수를 반환합니다.

• 쌍의 개수를 저장할 변수 count를 0으로 초기화합니다.

• for 반복문을 사용해 a 값을 하나씩 탐색합니다.

• a는 1부터 √n(n의 제곱근) 이하까지 순회합니다.

• b의 제곱을 bsquare = n − pow(a, 2)로 계산합니다.

• b = √bsquare 로 b의 값을 구합니다.

• pow(b, 2) == bsquare 이면 b가 정수이므로 count를 1 증가시킵니다.

• 모든 반복이 끝나면 count에는 조건을 만족하는 쌍의 총 개수가 저장됩니다.

• count를 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int squareSum(int n){
    int count = 0;
    for (int a = 1; a <= sqrt(n); a++){
        int bsquare = n - pow(a, 2);
        int b = sqrt(bsquare);
        if (pow(b, 2) == bsquare){
            count++;
        }
    }
    return count;
}

int main(){
    int N = 5;
    cout << "Count of pairs of (a,b) where a^2+b^2=N: " << squareSum(N);
    return 0;
}

※ 원본 코드에 포함되어 있던 디버깅용 출력문(cout << a;)은 결과를 깔끔하게 보여주기 위해 제거했습니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of pairs of (a,b) where a^2+b^2=N: 2

N = 5일 때, 1² + 2² = 1 + 4 = 5를 만족하는 쌍 (1, 2)와 (2, 1), 총 2개의 순서쌍이 존재합니다.

시간 복잡도

이 알고리즘은 a를 1부터 √N까지만 순회하므로 시간 복잡도는 O(√N)입니다. N이 커지더라도 효율적으로 동작하며, 추가 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.