Huyền thoại bốn bình phương Euler (Euler's Four Square Identity) trong C++

Trong bài toán này, chúng ta được cho hai số và cần tìm tích của chúng bằng cách sử dụng Huyền thoại bốn bình phương của Euler.

Huyền thoại bốn bình phương Euler phát biểu rằng: Nếu hai số a và b đều có thể biểu diễn dưới dạng tổng của bốn bình phương, thì tích a * b cũng có thể biểu diễn dưới dạng tổng của bốn bình phương.

Cụ thể:

a = x₁² + x₂² + x₃² + x₄²
b = y₁² + y₂² + y₃² + y₄²
a * b = z₁² + z₂² + z₃² + z₄²

Ví dụ minh họa

Đầu vào:

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

Đầu ra: 1² + 1² + 3² + 23² (trong nhiều kết quả có thể)

Giải thích: Tích a*b = 540. 540 = 1 + 1 + 9 + 529 = 1² + 1² + 3² + 23².

Phương pháp giải

Vì bài toán yêu cầu tìm một cách biểu diễn tích dưới dạng 4 bình phương, ta có thể dùng phương pháp vét cạn (brute-force) với 4 vòng lặp lồng nhau (hoặc 3 vòng lặp + kiểm tra căn bậc 2) để tìm các bộ số (x, y, z, k) thỏa mãn x² + y² + z² + k² = a*b.

Chương trình 1: 4 vòng lặp lồng nhau (Đơn giản)

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

void findEulerSquareValue(int a, int b) {
    int prod = a * b;
    int limit = sqrt(prod);

    for (int x = 0; x <= limit; x++) {
        for (int y = x; y <= limit; y++) {
            for (int z = y; z <= limit; z++) {
                for (int k = z; k <= limit; k++) {
                    int sum = x*x + y*y + z*z + k*k;
                    if (sum == prod) {
                        cout << "Tích " << a << "*" << b << " = " << prod
                             << " = " << x << "² + " << y << "² + " << z << "² + " << k << "²" << endl;
                    }
                }
            }
        }
    }
}

int main() {
    int a = 2*2 + 3*3 + 4*4 + 5*5; // 54
    int b = 1*1 + 2*2 + 1*1 + 2*2; // 10
    cout << "a = 54, b = 10" << endl;
    findEulerSquareValue(a, b);
    return 0;
}

Chương trình 2: Tối ưu với 3 vòng lặp (Kiểm tra số chính phương)

Giảm độ phức tạp bằng cách tính tổng 3 bình phương, phần còn lại phải là bình phương của một số nguyên.

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

void findEulerSquareValueOptimized(int a, int b) {
    int prod = a * b;
    int limit = sqrt(prod);

    for (int x = 0; x <= limit; x++) {
        for (int y = x; y <= limit; y++) {
            for (int z = y; z <= limit; z++) {
                int sum3 = x*x + y*y + z*z;
                int rem = prod - sum3;
                if (rem < 0) break;
                int k = sqrt(rem);
                if (k * k == rem && k >= z) { // Đảm bảo k >= z để tránh trùng lặp hoán vị
                    cout << "Tích " << a << "*" << b << " = " << prod
                         << " = " << x << "² + " << y << "² + " << z << "² + " << k << "²" << endl;
                }
            }
        }
    }
}

int main() {
    int a = 54, b = 10;
    findEulerSquareValueOptimized(a, b);
    return 0;
}

Đầu ra (Một phần)

Tích 54*10 = 540 = 1² + 1² + 3² + 23²
Tích 54*10 = 540 = 1² + 3² + 13² + 19²
Tích 54*10 = 540 = 2² + 4² + 6² + 22²
... (và nhiều kết quả khác)