C++로 구현하는 오일러 네 제곱 항등식: 두 수의 곱을 네 제곱수의 합으로 나타내기

이 문제에서는 두 개의 수가 주어졌을 때, 오일러 네 제곱 항등식(Euler's Four Square Identity)을 이용하여 두 수의 곱을 구해야 합니다.

오일러 네 제곱 항등식은 두 수 각각이 네 정수의 제곱합으로 표현될 수 있다면, 그 두 수의 곱 역시 어떤 네 정수의 제곱합으로 표현할 수 있다는 정리입니다. 참고로 라그랑주의 네 제곱수 정리(Lagrange's four-square theorem)에 따르면 모든 자연수는 네 제곱수의 합으로 표현될 수 있으므로, 이 항등식은 임의의 두 자연수에 대해서도 성립합니다.

두 수 a, b가 다음과 같이 주어질 때,

a = x1² + x2² + x3² + x4²
b = y1² + y2² + y3² + y4²

곱 a × b를 다음 형태로 만족하는 z1, z2, z3, z4를 찾는 것이 목표입니다.

a × b = z1² + z2² + z3² + z4²

예제로 문제 이해하기

입력:

a = 54 = 2*2 + 3*3 + 4*4 + 5*5
b = 10 = 1*1 + 2*2 + 1*1 + 2*2

출력: 1*1 + 1*1 + 3*3 + 23*23

설명: a와 b의 곱은 540이며, 540은 여러 가지 방법으로 네 제곱수의 합으로 표현할 수 있습니다. 그중 하나의 해는 다음과 같습니다.

540 = 1*1 + 1*1 + 3*3 + 23*23 = 1 + 1 + 9 + 529

풀이 접근 방법 1 — 완전 탐색(4중 반복문)

가장 단순한 풀이는 시행(trial) 방식으로, 가능한 네 제곱수 조합을 하나씩 모두 시도해 보는 것입니다. 이를 위해 각 제곱수 값마다 하나씩, 총 4개의 중첩 반복문을 사용하고 계산된 합이 두 수의 곱과 일치하면 해당 조합을 출력합니다.

이 방법은 직관적이지만 시간 복잡도가 O((a*b)⁴)에 비례하여 다소 비효율적이라는 단점이 있습니다.

구현 예제

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

void findEulerSquareNumberValue(int a, int b) {

    int prod = a * b;
    int sumSquare = 0;
    for (int x = 0; x <= sqrt(prod); x++) {
        for (int y = x; y <= sqrt(prod); y++) {
            for (int z = y; z <= sqrt(prod); z++) {
                for (int k = z; k <= sqrt(prod); k++) {

                    sumSquare = (x*x) + (y*y) + (z*z) + (k*k);
                    if (sumSquare == prod) {
                        cout << "The product " << a << "*" << b << " = " << prod << " represented as ";
                        cout << x << "*" << x << " + ";
                        cout << y << "*" << y << " + ";
                        cout << z << "*" << z << " + ";
                        cout << k << "*" << k << endl;
                        cout << endl;
                    }
                }
            }
        }
    }
}

int main() {

    int a = (2*2) + (3*3) + (4*4) + (5*5);
    int b = (1*1) + (2*2) + (1*1) + (2*2);
    cout << "a = (2*2) + (3*3) + (4*4) + (5*5) = " << a << endl;
    cout << "b = (1*1) + (2*2) + (1*1) + (2*2) = " << b << endl;
    findEulerSquareNumberValue(a, b);

    return 0;
}

실행 결과

a = (2*2) + (3*3) + (4*4) + (5*5) = 54
b = (1*1) + (2*2) + (1*1) + (2*2) = 10
The product 54*10 = 540 represented as 1*1 + 1*1 + 3*3 + 23*23
The product 54*10 = 540 represented as 1*1 + 3*3 + 13*13 + 19*19
The product 54*10 = 540 represented as 1*1 + 5*5 + 15*15 + 17*17
...
The product 54*10 = 540 represented as 9*9 + 11*11 + 13*13 + 13*13
The product 54*10 = 540 represented as 10*10 + 10*10 + 12*12 + 14*14

위 예제에서는 총 21가지 조합이 출력되며, 각 조합은 오름차순(x ≤ y ≤ z ≤ k)으로 탐색되므로 순서만 다른 중복 조합은 나타나지 않습니다.

풀이 접근 방법 2 — 최적화(3중 반복문)

시간 복잡도를 줄이는 더 효율적인 방법은 세 개의 중첩 반복문만 사용하는 것입니다. 앞의 세 제곱수(x, y, z)를 정한 뒤, 남은 값(prod − x² − y² − z²)이 완전제곱수인지만 확인하면 됩니다. 완전제곱수라면 그 제곱근이 네 번째 수가 되고, 그렇지 않다면 해당 조합은 해가 될 수 없습니다. 이처럼 네 번째 반복문을 제거하면 시간 복잡도를 O((a*b)³) 수준으로 낮출 수 있어 훨씬 효율적입니다.

구현 예제

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

void findEulerSquareNumberValue(int a, int b) {

    int prod = a * b;
    int sumSquare = 0;
    for (int x = 0; x <= sqrt(prod); x++) {
        for (int y = x; y <= sqrt(prod); y++) {
            for (int z = y; z <= sqrt(prod); z++) {

                sumSquare = (x*x) + (y*y) + (z*z);
                float k = sqrt(prod - sumSquare);
                if (floor(k) == ceil(k)) {
                    cout << "The product " << a << "*" << b << " = " << prod << " represented as ";
                    cout << x << "*" << x << " + ";
                    cout << y << "*" << y << " + ";
                    cout << z << "*" << z << " + ";
                    cout << k << "*" << k << endl;
                    cout << endl;
                }
            }
        }
    }
}

int main() {

    int a = (2*2) + (3*3) + (4*4) + (5*5);
    int b = (1*1) + (2*2) + (1*1) + (2*2);
    cout << "a = (2*2) + (3*3) + (4*4) + (5*5) = " << a << endl;
    cout << "b = (1*1) + (2*2) + (1*1) + (2*2) = " << b << endl;
    findEulerSquareNumberValue(a, b);

    return 0;
}

실행 결과

a = (2*2) + (3*3) + (4*4) + (5*5) = 54
b = (1*1) + (2*2) + (1*1) + (2*2) = 10
The product 54*10 = 540 represented as 1*1 + 1*1 + 3*3 + 23*23
The product 54*10 = 540 represented as 1*1 + 3*3 + 13*13 + 19*19
The product 54*10 = 540 represented as 1*1 + 5*5 + 15*15 + 17*17
...
The product 54*10 = 540 represented as 11*11 + 13*13 + 15*15 + 5*5
The product 54*10 = 540 represented as 12*12 + 14*14 + 14*14 + 2*2

이 방식은 네 번째 값을 반복문으로 고정하지 않고 제곱근 계산으로 유도하기 때문에, 같은 조합이 순서만 다르게 여러 번 출력될 수 있다는 점에 유의하세요. 필요하다면 k ≥ z 조건을 추가하여 중복 출력을 제거할 수 있습니다.

마무리

오일러 네 제곱 항등식은 수학적으로 흥미로울 뿐만 아니라, 완전 탐색 구조를 어떻게 최적화할 수 있는지 보여주는 좋은 프로그래밍 연습 문제이기도 합니다. 핵심 아이디어는 마지막 값을 반복문으로 찾는 대신 '완전제곱수 판별'로 처리하여 탐색 공간을 한 차원 줄이는 것입니다.