1. Tóm tắt đề bài

Cho hai số nguyên dương ~a~ và ~b~ (~a \le b~). Hãy tìm một số nằm trong đoạn ~[a, b]~ có số lượng ước số nguyên dương là nhiều nhất. Nếu có nhiều số cùng đạt số lượng ước lớn nhất, in ra số có giá trị nhỏ nhất.

• Dữ liệu vào (Input):
  • Một dòng chứa hai số nguyên dương ~a, b~ cách nhau bởi dấu cách (~1 \le a \le b \le 10^4~).
• Dữ liệu ra (Output):
  • Hai số nguyên cách nhau bởi một dấu cách: số tìm được và số lượng ước của nó.

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:

  • ~1 \le a \le b \le 10^4~.
  • Số lượng số cần xét trong đoạn ~[a, b]~ tối đa là ~10^4~ số.
  • Với mỗi số ~x \le 10^4~, ta có thể đếm số lượng ước bằng cách duyệt ~i~ từ ~1~ đến ~\sqrt{x}~. Vì ~\sqrt{x} \le 100~, thao tác đếm ước cho một số chỉ tốn tối đa ~100~ phép tính.

• Đánh giá thời gian & Bộ nhớ:

  • Tổng số phép tính để xét toàn bộ đoạn ~[a, b]~ là: ~(b - a + 1) \times \sqrt{b} \le 10^4 \times 100 = 10^6 \text{ phép tính}~
  • Máy tính xử lý được ~\approx 10^8~ phép tính/giây, do đó thuật toán chạy mất chưa tới ~0.02~ giây, tối ưu tuyệt đối và không bị quá thời gian.
  • Các giá trị đều nằm trong phạm vi ~10^4~, hoàn toàn sử dụng kiểu dữ liệu số nguyên thông thường 32-bit (int).

3. Thuật toán xử lý

• Ý tưởng:

  1. Xây dựng hàm int demuoc(int n) để đếm số lượng ước của số ~n~:
     • Khởi tạo int cnt = 0;.
     • Duyệt ~i~ từ ~1~ đến ~\sqrt{n}~ (điều kiện i * i <= n):
       • Nếu n % i == 0:
         • Nếu ~i \times i = n~ (ước trùng nhau): tăng cnt lên ~1~.
         • Ngược lại (~i~ và ~n / i~ là hai ước phân biệt): tăng cnt lên ~2~.
     • Trả về kết quả cnt.
  2. Trong hàm main:
     • Nhập chuẩn hai số ~a, b~: cin >> a >> b;.
     • Khởi tạo:
       • uocmax = -1 (lưu số lượng ước lớn nhất).
       • socantim = a (lưu số có số lượng ước lớn nhất).
     • Duyệt ~i~ tăng dần từ ~a~ đến ~b~:
       • Tính souoc = demuoc(i);.
       • Lưu ý quan trọng về điều kiện cập nhật: Vì duyệt ~i~ từ bé đến lớn và đề bài yêu cầu "nếu có nhiều số cùng số lượng ước lớn nhất, in ra số có giá trị nhỏ nhất", ta chỉ cập nhật khi gặp số có số lượng ước lớn hơn hẳn (souoc > uocmax):
         • uocmax = souoc;
         • socantim = i;
     • In ra socantim và uocmax cách nhau bởi dấu cách, kết thúc bằng cout << endl;.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}((b - a + 1) \cdot \sqrt{b})~ — Duyệt qua tối đa ~10^4~ số, kiểm tra đến ~\sqrt{n}~. Chạy tức thì (~< 0.02~ giây).
  • Không gian (bộ nhớ): ~\mathcal{O}(1)~ — Chỉ dùng vài biến đơn lẻ.

4. Mã nguồn cài đặt (C++)

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

// Hàm đếm số lượng ước nguyên dương của n
int demuoc(int n) {
    int cnt = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (i * i == n) {
                cnt++;
            } else {
                cnt += 2;
            }
        }
    }
    return cnt;
}

int main() {
    // Tối ưu nhập/xuất chuẩn
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b;
    cin >> a >> b;

    int uocmax = -1;
    int socantim = a;

    for (int i = a; i <= b; i++) {
        int souoc = demuoc(i);
        // Chỉ cập nhật khi số lượng ước lớn hơn hẳn để giữ lại số nhỏ nhất
        if (souoc > uocmax) {
            uocmax = souoc;
            socantim = i;
        }
    }

    cout << socantim << " " << uocmax << endl;

    return 0;
}