Hiểu bài toán

Cho một số nguyên dương N. Tìm hai số nguyên dương a và b sao cho a * b = N và hiệu |a - b| là nhỏ nhất. Nếu có nhiều cặp (a, b) thỏa mãn, in ra cặp có a nhỏ nhất. Về bản chất, đây là bài toán tìm hai cạnh của hình chữ nhật có diện tích N sao cho chúng gần nhau nhất, tương đương với việc tìm ước của N nằm gần nhất với căn bậc hai của N.

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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;

    long long a = 1, b = n;

    for (long long i = sqrt(n); i >= 1; i--) {
        if (n % i == 0) {
            a = i;
            b = n / i;
            break;
        }
    }

    cout << a << " " << b;
    return 0;
}

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

Đây là cách tiếp cận hiệu quả nhất trong các giải pháp được cung cấp. Ý tưởng là hai số a và b càng gần nhau thì hiệu của chúng càng nhỏ. Do đó, a và b phải nằm gần căn bậc hai của N nhất có thể. Ta duyệt i từ floor(sqrt(N)) giảm dần về 1. Khi tìm được i đầu tiên là ước của N (n % i == 0), thì i là số lớn nhất trong các số nhỏ hơn hoặc bằng sqrt(N) chia hết cho N. Do đó, cặp (i, N/i) sẽ là cặp ước có hiệu nhỏ nhất. Vòng lặp kết thúc ngay khi tìm thấy cặp đầu tiên.

Cách Duyệt toàn bộ các ước số

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    long long a = 1, b = n;
    for ( long long i = 1 ; i * i <= n ; i++ )
    {
        if ( n % i == 0 )
        {
            long long j = n / i;
            if ( j - i < b - a )
            {
                a = i;
                b = j;
            }
        }
    }
    cout << a << " " << b;
}

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

Cách tiếp cận này duyệt qua tất cả các ước số i của N từ 1 đến sqrt(N). Với mỗi i là ước, nó tính j = N/i. Sau đó, nó so sánh hiệu j - i với hiệu của cặp ước tốt nhất tìm được jusqu'at hiện tại (b - a). Nếu hiệu nhỏ hơn, nó cập nhật cặp (a, b). Cách này cũng có độ phức tạp O(sqrt(N)) nhưng thực hiện nhiều phép so sánh và gán hơn so với cách đầu tiên vì nó phải duyệt hết tất cả các ước số trong khoảng [1, sqrt(N)] thay vì dừng lại ở ước gần sqrt(N) nhất.

Cách Brute Force (Tối ưu kém)

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

int main() {
    long long n;
    cin >> n;
    for (long long i = 1; i <= n; i++) {
        if (n % i == 0) {
            cout << i << " " << n / i;
            return 0;
        }
    }
    return 0;
}

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

Đây là một cách suy nghĩ đơn giản nhưng không được dùng trong các giải pháp đã cho, nhưng có thể suy ra từ logic duyệt ước. Nếu ta duyệt i từ 1 đến N, và in ra cặp (i, N/i) ngay khi gặp ước đầu tiên, ta sẽ được (1, N). Tuy nhiên, để tối ưu hóa theo yêu cầu bài toán, nếu ta muốn tìm cặp có hiệu nhỏ nhất bằng cách duyệt tất cả cặp (a, b) sao cho a*b=N, ta phải duyệt i từ 1 đến N. Độ phức tạp O(N) quá chậm so với O(sqrt(N)). Do đó, đây là một hướng tiếp cận sai lệch nếu không tối ưu vòng lặp.

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

Bài học kinh nghiệm

• Bài toán tìm hai số a, b sao cho a * b = N và |a - b| nhỏ nhất thực chất là tìm hai ước của N nằm gần căn bậc hai của N nhất.
• Chỉ cần duyệt các ước số từ 1 đến sqrt(N) là đủ để tìm ra tất cả các cặp ước.
• Sử dụng long long là bắt buộc để xử lý các số lớn.

Lỗi thường gặp

• Chọn sai hướng duyệt (tăng dần thay vì giảm dần)导致 in ra cặp (1, N) thay vì cặp tối ưu.
• Sử dụng int thay vì long long dẫn đến tràn số với输入 lớn.
• Tính toán sai giới hạn vòng lặp (ví dụ: i < sqrt(n) thay vì i * i <= n hoặc i <= sqrt(n)).