Hiểu bài toán

Cho một số nguyên dương N. Tìm ba số nguyên dương a, b, c khác nhau, không vượt quá N, sao cho Bội Chung Nhỏ Nhất (LCM) của chúng là lớn nhất có thể. Nếu có nhiều bộ ba, in ra giá trị LCM lớn nhất đó.

Dữ liệu: N ≤ 10^6 (theo các giải pháp chấp nhận).

Ví dụ:

• N = 3 -> Các số 1, 2, 3 -> LCM = 6.
• N = 4 -> Các số 1, 2, 3 có LCM = 6; các số 2, 3, 4 có LCM = 12. -> Đáp án là 12.

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

Cách Brute Force (Tìm kiếm toàn bộ)

#include <iostream>
#include <algorithm>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    long long n;
    cin >> n;
    long long ans = 0;
    for (long long i = 1; i <= n; ++i) {
        for (long long j = i + 1; j <= n; ++j) {
            for (long long k = j + 1; k <= n; ++k) {
                ans = max(ans, lcm(lcm(i, j), k));
            }
        }
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(N^3)
• Space Complexity: O(1)

Giải pháp này thử tất cả các tổ hợp 3 số khác nhau từ 1 đến N, tính LCM và tìm giá trị lớn nhất. Phương pháp này đúng nhưng cực kỳ chậm, chỉ phù hợp với N rất nhỏ (ví dụ < 50).

Cách Quy tắc tối ưu hóa (Heuristic)

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

int main() {
    long long n;
    cin >> n;
    if (n <= 2) {
        cout << n;
        return 0;
    }
    if (n % 2 != 0) { // N lẻ
        cout << n * (n - 1) * (n - 2);
    } else { // N chẵn
        long long ans1 = (n - 1) * (n - 2) * (n - 3);
        long long ans2 = n * (n - 1) * (n - 3) / __gcd(n, n - 3);
        cout << max(ans1, ans2);
    }
    return 0;
}

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

Tiếp cận dựa trên quan sát toán học:

1. Nếu N là số lẻ: 3 số N, N-1, N-2 là 3 số chẵn-lẻ-lẻ liên tiếp. N-1 và N-2 coprime (vì chênh lệch 1). N coprime với cả N-1 và N-2. Do đó LCM = N * (N-1) * (N-2). Đây là giá trị lớn nhất có thể vì các số nằm ở đầu dãy.
2. Nếu N là số chẵn: N, N-1, N-2 không tối ưu vì N và N-2 đều chẵn, chia hết cho 2, giảm LCM. Ta có 2 lựa chọn:
   • Bỏ N, lấy (N-1), (N-2), (N-3): LCM = (N-1)(N-2)(N-3).
   • Bỏ N-2, lấy N, (N-1), (N-3): LCM = N(N-1)(N-3) / gcd(N, N-3). So sánh 2 giá trị này và chọn cái lớn hơn.

Phân tích chi tiết Solution 3 (a1n_s4m4): Code này có vẻ ngắn gọn nhưng logic hơi khác một chút:

• N lẻ: In N(N-1)(N-2).
• N chẵn:
  • Nếu N chia hết cho 3: In (N-3)(N-2)(N-1). (Lý do: N chẵn và chia hết cho 3 thì N-3 cũng chẵn và chia hết cho 3, nên N và N-3 có gcd >= 2, làm giảm LCM của bộ N, N-1, N-3. Do đó bộ N-1, N-2, N-3 tốt hơn).
  • Nếu N không chia hết cho 3: In (N-3)N(N-1). (Lý do: N không chia hết cho 3, nên gcd(N, N-3) = gcd(N, 3). Vì N chẵn nên gcd = 1 hoặc 2. Nếu N không chia hết cho 3, gcd(N, 3) = 1 hoặc 2. Nếu N chẵn không chia hết cho 3, N có thể chia hết cho 2. N-3 là số lẻ (vì N chẵn). Vậy gcd(N, N-3) = 1). Do đó LCM = N(N-1)(N-3).

Các giải pháp khác (Solution 1 & 2) cũng bám sát logic này.

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

Bài học kinh nghiệm

• Đối với các bài toán tối ưu hóa trên dãy số tự nhiên liên tiếp, các số lớn nhất thường là ứng cử viên sáng giá nhất.
• Nếu N là số lẻ, đáp án luôn là N * (N-1) * (N-2) vì 3 số này pairwise coprime (hoặc chỉ cần gcd chung là 1 để sản phẩm là bội chung).
• Khi N là số chẵn, ta phải loại bỏ ít nhất một số chẵn để tránh giảm giá trị LCM do thừa số 2. Cần so sánh hai trường hợp: loại N hoặc loại N-2.

Lỗi thường gặp

• Sử dụng sai công thức LCM: LCM(a, b) = (a * b) / GCD(a, b). Cần chú ý thứ tự tính toán để tránh tràn số, nên viết là a / GCD(a, b) * b.
• Quên xử lý các trường hợp N nhỏ (N < 3) dẫn đến lỗi truy cập mảng âm hoặc vòng lặp không có phần tử.
• Biên độ số lớn: Với N lên tới 10^6, kết quả có thể lên tới ~10^18, bắt buộc phải sử dụng kiểu dữ liệu 64-bit (long long trong C++).