Hiểu bài toán

Cho một số nguyên dương n (1 ≤ n ≤ 10^15). Tìm hai số nguyên dương a, b sao cho a * b = n và |a - b| là nhỏ nhất. Nói cách khác, cần tìm hai thừa số của n càng gần nhau càng tốt. Ví dụ với n = 8, các cặp (1,8), (2,4) thì cặp (2,4) có độ chênh lệch là 2, nhỏ hơn độ chênh lệch 7 của cặp (1,8), nên đáp án là (2,4).

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

Cách Duyệt từ căn bậc hai của n

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    for (long long i = trunc(sqrt(n)); i >= 1; i--)
    {
        if (n % i == 0)
        {
            cout << i << ' ' << n / i;
            return 0;
        }
    }
    return 0;
}

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

Để tìm hai thừa số a và b (a ≤ b) có hiệu |a - b| nhỏ nhất, ta cần tìm a càng gần √n càng tốt. Nếu a < √n thì b = n/a > √n, và khoảng cách a - b = a - n/a sẽ rất lớn. Do đó, ta chỉ cần duyệt các số i từ ⌊√n⌋ giảm dần về 1. Số i đầu tiên mà chia hết cho n chính là a (thừa số nhỏ nhất trong các cặp có một thừa số gần √n nhất), và b = n / i. Vòng lặp này sẽ chạy tối đa √n lần. Với n = 10^15 thì √n ≈ 10^7.5, đây là số lượng phép tính lớn nhưng vẫn có thể chạy trong thời gian giới hạn (khoảng 1-2 giây) của các kỳ thi lập trình thông thường.

Cách Cải tiến vòng lặp (tối ưu hằng số)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, s;
    cin >> n;
    s = sqrt(n);
    while (n % s != 0)
        s -= 1;
    cout << s << " " << n / s;
}

• Time Complexity: O(√n) (trung bình tốt hơn)
• Space Complexity: O(1)

Giải thuật này cũng dựa trên ý tưởng tìm thừa số gần √n nhất, nhưng thay vì dùng câu lệnh for với bước nhảy 1, nó dùng while để kiểm tra. Tuy nhiên, xét về độ phức tạp thuật toán, nó vẫn là O(√n) trong trường hợp xấu nhất (ví dụ n là số nguyên tố). Trong một số trường hợp may mắn, số cần tìm nằm ngay gần √n, vòng lặp sẽ dừng sớm. Tuy nhiên, so với phương pháp duyệt for giảm dần, phương pháp này không đảm bảo tìm được cặp (a, b) có độ chênh lệch nhỏ nhất một cách trực quan bằng cách duyệt từ trên xuống. Dù vậy, về mặt lý thuyết, cả hai đều là O(√n).

Cách Phương pháp tối ưu (kiểm tra tính nguyên tố trước)

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

ll n;
bool kiem_tra_nguyen_to(ll n)
{
    if (n < 2 || n == 4) return false;
    if (n > 5)
    {
        if (n % 2 == 0 || n % 3 == 0) return false;
        int can = sqrt(n);
        for (int i = 5; i <= can; i += 6)
        {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    if (kiem_tra_nguyen_to(n) == true)
    {
        cout << 1 << ' ' << n;
    }
    else
    {
        for (int i = sqrt(n); i > 0; i--)
        {
            if (n % i == 0)
            {
                cout << i << ' ' << n / i;
                return 0;
            }
        }
    }
    return 0;
}

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

Giải thuật này thêm một bước kiểm tra ban đầu: nếu n là số nguyên tố thì đáp án luôn là (1, n). Việc kiểm tra số nguyên tố có thể thực hiện trong thời gian O(√n). Nếu n không phải số nguyên tố, nó mới thực hiện vòng lặp duyệt từ √n trở xuống. Trong trường hợp n là số nguyên tố, giải thuật này sẽ chạy nhanh hơn một chút so với việc duyệt ngay lập tức. Tuy nhiên, trong trường hợp xấu nhất (n là số hợp số lớn), độ phức tạp vẫn là O(√n).

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

Bài học kinh nghiệm

• Hai số a và b có tích bằng n mà hiệu |a - b| nhỏ nhất sẽ nằm càng gần √n càng tốt.
• Tìm thừa số của n bắt đầu từ căn bậc hai của nó và đi lùi về 1 là cách hiệu quả nhất để tìm ra cặp số này mà không cần kiểm tra tất cả các cặp.

Lỗi thường gặp

• Sử dụng biến kiểu int cho biến lưu trữ n, vì n có thể lên tới 10^15, cần dùng long long.
• Sai lệch trong tính toán căn bậc hai do số thực (ví dụ: sqrt(n) trả về 999999.999999 khi n là số chính phương lớn, sau khi casting về int sẽ thành 999999, bỏ sót thừa số 1000000). Cần dùng trunc(sqrt(n)) hoặc công thức pow(n, 0.5) và kiểm tra kỹ lưỡng.