Hiểu bài toán

Bài toán yêu cầu tìm số nguyên dương đặc biệt đầu tiên lớn hơn hoặc bằng một số nguyên dương N cho trước. Một số được gọi là 'đặc biệt' nếu nó có đúng 4 ước số. Ví dụ: 6 (các ước: 1, 2, 3, 6) và 8 (các ước: 1, 2, 4, 8) là các số đặc biệt. Nhu cầu là tìm số đặc biệt nhỏ nhất >= N.

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

Cách Brute Force - Kiểm tra từng số (Đếm ước)

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

// Hàm đếm số lượng ước số của n
int countDivisors(int n) {
    int count = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            // Nếu i là ước thì n/i cũng là ước
            if (n / i == i)
                count += 1; // i là ước kép (vd: n=9, i=3)
            else
                count += 2;
        }
    }
    return count;
}

int main() {
    freopen("number.inp", "r", stdin);
    freopen("number.out", "w", stdout);

    int n;
    cin >> n;

    // Duyệt từ n trở đi cho đến khi tìm thấy số đặc biệt
    while (true) {
        if (countDivisors(n) == 4) {
            cout << n;
            break;
        }
        n++;
    }

    return 0;
}

• Time Complexity: O(K * sqrt(N)), với K là khoảng cách từ N đến số đặc biệt tiếp theo
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Ta bắt đầu từ số N và lần lượt kiểm tra từng số nguyên dương lớn hơn (N, N+1, N+2,...). Với mỗi số, ta đếm tất cả các ước số của nó. Nếu số lượng ước bằng 4, ta in ra số đó và dừng lại.

Cách đếm ước:

• Duyệt i từ 1 đến căn bậc hai của số đang xét.
• Nếu i chia hết cho số đó, thì i và số đó/i đều là ước.
• Nếu i bằng số đó/i (khi số là bình phương của i), chỉ cộng 1 vào biến đếm, ngược lại cộng 2.

Phương pháp này đảm bảo tìm được kết quả chính xác, nhưng hiệu quả phụ thuộc vào việc số đặc biệt nằm cách N bao xa.

Cách Tối ưu - Kiểm tra theo tính chất số học

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

// Hàm kiểm tra số nguyên tố
bool isPrime(long long x) {
    if (x < 2) return false;
    if (x % 2 == 0) return x == 2;
    for (long long i = 3; i * i <= x; i += 2)
        if (x % i == 0) return false;
    return true;
}

// Hàm kiểm tra có phải số đặc biệt không dựa trên tính chất
bool isSpecial(long long k) {
    // Kiểm tra dạng p^3 (bình phương p * p * p)
    long long r = round(pow(k, 1.0/3));
    if (r*r*r == k && isPrime(r)) return true;

    // Kiểm tra dạng p * q (tích hai số nguyên tố phân biệt)
    for (long long p = 2; p * p <= k; p++) {
        if (k % p == 0) {
            long long q = k / p;
            // p < q để đảm bảo p và q phân biệt và chỉ kiểm tra 1 lần
            if (p < q && isPrime(p) && isPrime(q)) 
                return true;
            // Nếu tách được thành p*q nhưng q không nguyên tố hoặc p=q, 
            // thì k không có dạng p*q phân biệt hay p^3.
            // Nếu k không chia hết cho số nào < sqrt(k), nó là số nguyên tố (chỉ 2 ước).
            return false;
        }
    }
    return false;
}

int main() {
    long long n;
    cin >> n;

    long long k = n;
    while (!isSpecial(k)) k++;

    cout << k;
    return 0;
}

• Time Complexity: O(sqrt(N)) cho mỗi lần kiểm tra (trong trường hợp xấu nhất)
• Space Complexity: O(1)

Một số có đúng 4 ước số phải thuộc một trong hai dạng:

1. Số có dạng p^3, với p là số nguyên tố. (Ước: 1, p, p^2, p^3)
2. Số có dạng p * q, với p và q là hai số nguyên tố khác nhau. (Ước: 1, p, q, p*q)

Thay vì đếm tất cả các ước, ta có thể kiểm tra xem số đó có thuộc một trong hai dạng trên hay không:

• Kiểm tra dạng p^3: Tính căn bậc 3 của số, nếu bình phương của căn bậc 3 bằng số đó và căn bậc 3 là số nguyên tố thì đúng.
• Kiểm tra dạng p*q: Duyệt tìm ước nhỏ nhất p (từ 2 đến căn bậc 2 của số). Nếu tìm thấy ước p, kiểm tra xem p và k/p có phải là hai số nguyên tố khác nhau không. Nếu có, đó là số đặc biệt. Nếu không, số đó không phải là số đặc biệt (vì nếu có thêm ước khác, nó sẽ có nhiều hơn 4 ước).

Cách này loại bỏ việc đếm các ước thừa, tập trung vào cấu trúc của số đặc biệt.

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

Bài học kinh nghiệm

• Một số nguyên dương có đúng 4 ước số nếu và chỉ nếu nó thuộc một trong hai dạng: p^3 (bình phương của một số nguyên tố p) hoặc p * q (tích của hai số nguyên tố phân biệt p và q).
• Đối với bài toán tìm số đặc biệt >= N, ta có thể bắt đầu từ N và lần lượt kiểm tra các số kế tiếp cho đến khi tìm thấy.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu quá nhỏ (ví dụ: int thay vì long long) có thể gây tràn số khi N lớn hoặc khi tính bình phương/căn bậc ba.
• Trong thuật toán đếm ước, cần chú ý xử lý trường hợp số là bình phương chính phương (vd: 9) để không đếm trùng ước.
• Khi kiểm tra dạng p * q, cần đảm bảo p và q là hai số nguyên tố khác nhau. Nếu p = q, số đó là p^2, chỉ có 3 ước (1, p, p^2).