เอกลักษณ์สี่เหลี่ยมจัตุรัสของออยเลอร์ (Euler's Four Square Identity) ใน C++

ปัญหา

ได้รับสองจำนวน ต้องหาผลคูณโดยใช้เอกลักษณ์สี่เหลี่ยมจัตุรัสของออยเลอร์ ซึ่งระบุว่าผลคูณของสองจำนวนที่แสดงเป็นผลรวมของสี่กำลังสอง สามารถแสดงเป็นผลรวมของสี่กำลังสองได้อีกครั้ง

สูตร:

a = x1² + x2² + x3² + x4²
b = y1² + y2² + y3² + y4²
a * b = z1² + z2² + z3² + z4²

ตัวอย่าง

อินพุต: a = 54 = 2²+3²+4²+5², b = 10 = 1²+2²+1²+2²

เอาต์พุต: 1² + 1² + 3² + 23²

คำอธิบาย: ผลคูณ 540 = 1+1+9+529 = 540

แนวทางแก้ปัญหา

วิธีที่ 1: Brute Force (4 Nested Loops) ลองทุกชุดค่าที่เป็นไปได้ ความซับซ้อน O((a*b)⁴)

วิธีที่ 2: ปรับปรุง (3 Nested Loops + Perfect Square Check) ลดลูปเหลือ 3 ตัว ตรวจสอบค่าที่ 4 ว่าเป็นกำลังสองสมบูรณ์หรือไม่

โปรแกรมตัวอย่าง (วิธีที่ 2)

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

void findEulerSquareNumberValue(int a, int b) {
    int prod = a * b;
    for (int x = 0; x <= sqrt(prod); x++) {
        for (int y = x; y <= sqrt(prod); y++) {
            for (int z = y; z <= sqrt(prod); z++) {
                int 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 " << x << "*" << x << " + " 
                         << y << "*" << y << " + " << z << "*" << z << " + " 
                         << k << "*" << k << 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 = " << a << endl;
    cout << "b = " << b << endl;
    findEulerSquareNumberValue(a, b);
    return 0;
}

ผลลัพธ์

แสดงชุดค่าทั้งหมดที่ทำให้ 540 = ผลรวมของสี่กำลังสอง (มีหลายชุดคำตอบ)