Hiểu bài toán

Bài toán yêu cầu giải hệ phương trình bậc nhất hai ẩn (a1x + b1y = c1 và a2x + b2y = c2) với các hệ số nguyên có thể rất lớn (đến 10^9). Cần phân tích các trường hợp để tìm nghiệm:

1. Nghiệm duy nhất: Ma trận hệ số có định khác 0 (a1b2 != b1a2).
2. Vô số nghiệm: Hai phương trình tương đương (tỷ lệ hệ số bằng nhau và bằng tỷ lệ số tự do).
3. Vô nghiệm: Hai phương trình song song nhưng không trùng nhau (tỷ lệ hệ số bằng nhau nhưng không bằng tỷ lệ số tự do). Đặc biệt, yêu cầu in số thực làm tròn đến 2 chữ số thập phân nếu có nghiệm duy nhất.

Các cách tiếp cận

Cách Phân tích Ma trận (Determinant)

#include <stdio.h>

int main() {
    long long a, b, c, d, e, f;
    scanf("%lld %lld %lld %lld %lld %lld", &a, &b, &c, &d, &e, &f);

    long long D = a * e - b * d;
    long long Dx = c * e - b * f;
    long long Dy = a * f - c * d;

    if (D != 0) {
        // Nghiệm duy nhất
        // In số thực làm tròn 2 chữ số thập phân
        printf("%.2lf %.2lf\n", (double)Dx / D, (double)Dy / D);
    } else {
        if (Dx == 0 && Dy == 0) {
            printf("VOSONGHIEM\n");
        } else {
            printf("VONGHIEM\n");
        }
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận chuẩn sử dụng định lý Kramer (Cramer's Rule).

• Tính định thức của ma trận hệ số: $D = ae - bd$.
• Tính định thức thay thế cột x: $D_x = ce - bf$.
• Tính định thức thay thế cột y: $D_y = af - cd$.
• Trường hợp $D \neq 0$: Hệ có nghiệm duy nhất, $x = Dx / D$, $y = Dy / D$. Lưu ý ép kiểu double khi chia để không bị chia lấy thương số nguyên.
• Trường hợp $D = 0$: Ma trận hệ số suy biến.
  • Nếu cả $Dx$ và $Dy$ đều bằng 0, hai phương trình tương đương, có vô số nghiệm.
  • Ngược lại, hệ vô nghiệm. Cách này xử lý được tất cả các trường hợp bao gồm khi hệ số bằng 0 một cách chính xác.

Cách Xử lý Trực tiếp theo Tỷ lệ

#include <stdio.h>

int main() {
    long long a, b, c, d, e, f;
    scanf("%lld %lld %lld %lld %lld %lld", &a, &b, &c, &d, &e, &f);

    // Xử lý riêng trường hợp a và d đều bằng 0
    if (a == 0 && d == 0) {
        if (b * f == c * e) {
            if (b == 0 && e == 0) {
                 // 0x = c, 0x = f
                 if (c == f) printf("VOSONGHIEM"); else printf("VONGHIEM");
            } else {
                 printf("VOSONGHIEM");
            }
        } else {
            printf("VONGHIEM");
        }
        return 0;
    }

    // Tính tỷ lệ
    double k1 = 0, k2 = 0;
    int valid_k1 = 0, valid_k2 = 0;

    if (d != 0) {
        k1 = (double)a / d;
        valid_k1 = 1;
    } else if (a != 0) {
        // d=0, a!=0 -> song song doc doc (xu ly rieng hoac de logic Mac dinh)
    }

    if (e != 0) {
        k2 = (double)b / e;
        valid_k2 = 1;
    } else if (b != 0) {
        // e=0, b!=0
    }

    // Logic kiểm tra song song (tỷ lệ a/d == b/e)
    // Sử dụng nhân chéo để tránh chia 0
    if (a * e == b * d) {
        if (a * f == c * d) {
            printf("VOSONGHIEM");
        } else {
            printf("VONGHIEM");
        }
    } else {
        // Dùng Cramer để tính nhanh
        long long D = a * e - b * d;
        long long Dx = c * e - b * f;
        long long Dy = a * f - c * d;
        printf("%.2lf %.2lf\n", (double)Dx / D, (double)Dy / D);
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này thường bắt đầu bằng việc kiểm tra xem hai phương trình có song song hay không bằng cách so sánh các tỷ lệ hệ số ($a/d$ so với $b/e$). Tuy nhiên, để tránh lỗi chia cho 0 và lỗi số học khi một trong các hệ số bằng 0, ta nên sử dụng phép nhân chéo (ví dụ: $a \times e$ so với $b \times d$).

• Nếu $a \times e = b \times d$: Hai phương trình song song. Kiểm tra tiếp $a \times f = c \times d$ để phân biệt 'vô số nghiệm' hay 'vô nghiệm'.
• Nếu $a \times e \neq b \times d$: Hai phương trình cắt nhau, dùng công thức Cramer (hoặc giải trực tiếp) để tìm nghiệm. Phương pháp này logic với suy nghĩ con người nhưng code bẫy lỗi nhiều hơn giải pháp định thức nếu không cẩn thận.

Cách Thử và Sai (Dùng float - Không khuyến khích)

#include <stdio.h>
int main() {
    // Code mẫu lỗi từ Solution 1
    int a, b, c, d, e, f;
    scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
    if (d != 0) {
        // Logic sai lệch, không theo chuẩn toán học
        double x = 1.0 * e * a / d - b, y = 1.0 * f * a / d - c;
        // ... tiếp tục các phép so sánh x == 0
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Một số solutions thô (như Solution 1) đã cố gắng biến đổi phương trình theo cách không chuẩn (ví dụ: chia phương trình đầu cho d rồi trừ b...). Điều này rất nguy hiểm.

• Dễ bị sai số số học (floating point error).
• Logic xử lý các trường hợp đặc biệt (khi d=0, e=0...) bị rối rắm và dễ sai.
• So sánh số thực bằng x == 0 là thói quen xấu. Đây là ví dụ về cách tiếp cận không nên dùng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Sử dụng định thức là cách tổng quát và an toàn nhất để phân loại hệ phương trình bậc nhất. Ma trận hệ số $D = ae - bd$.
• Phép nhân chéo ($a \times e$ so với $b \times d$) là cách kiểm tra song song (vô số nghiệm/vô nghiệm) an toàn nhất, tránh chia cho 0.
• Phải ép kiểu double khi tính nghiệm ($x, y$) để đảm bảo kết quả là số thực, và dùng %.2lf để in đúng yêu cầu.

Lỗi thường gặp

• Lỗi chia cho 0: Khi chia trực tiếp các hệ số cho nhau để so sánh tỷ lệ (ví dụ: if (a/d == b/e)). Cần dùng nhân chéo thay thế.
• Sai số làm tròn: Nếu tính toán trên số nguyên hoàn toàn rồi mới ép kiểu, có thể mất độ chính xác. Nên ép kiểu sang double trước khi chia.
• Bỏ qua trường hợp ma trận suy biến ($D=0$): Cần kiểm tra kỹ xem khi $D=0$, hệ có nghiệm hay vô nghiệm dựa trên $Dx$ và $Dy$. Nếu chỉ in 'VÔ NGHIỆM' bừa bãi khi $D=0$ sẽ bị sai.