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

Cho 4 số nguyên dương ~n_1, n_2, n_3, n_4~. Với mỗi số nguyên ~n~, liệt kê tất cả các ước số nguyên dương của nó theo thứ tự tăng dần trên một dòng, dòng tiếp theo in ra tổng số lượng ước theo quy cách Tong so uoc: <so_luong>.

• Yêu cầu kỹ thuật: Bắt buộc xây dựng và sử dụng hàm void lietKeUoc(int n) để tìm, in các ước và số lượng ước của ~n~.
• Dữ liệu vào (UOCSO.INP): Gồm 4 dòng, mỗi dòng chứa một số nguyên dương ~n_i~ (~1 \le n_i \le 10^5~).
• Dữ liệu ra (UOCSO.OUT): Gồm 8 dòng (mỗi số ~n_i~ xuất ra 2 dòng):
  • Dòng 1: Các ước nguyên dương sắp xếp tăng dần, cách nhau bởi một khoảng trắng.
  • Dòng 2: Xâu định dạng Tong so uoc: <so_luong>.

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

• Giới hạn giá trị: ~n_i \le 10^5~.

  • Với ~n \le 10^5~, thuật toán duyệt cơ bản từ ~1~ đến ~n~ chỉ tốn tối đa ~10^5~ phép tính cho mỗi số.
  • Với 4 số, tổng số phép tính khoảng ~4 \times 10^5~, thời gian thực thi ~< 0.01~ giây (hoàn toàn vượt qua giới hạn thời gian tiêu chuẩn ~1.0~ giây).
  • Đối với các lớp học sinh giỏi nâng cao, có thể tối ưu duyệt đến ~\sqrt{n}~ rồi sắp xếp hoặc in theo 2 chiều, tuy nhiên với ~n \le 10^5~, cách duyệt trực tiếp từ ~1~ đến ~n~ là đơn giản, trực quan và tự động đảm bảo thứ tự tăng dần.

• Kiểu dữ liệu:

  • Giá trị ~n_i \le 10^5~ hoàn toàn nằm trong giới hạn của kiểu số nguyên thông thường 32-bit (int).

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

• Ý tưởng thiết kế hàm void lietKeUoc(int n):

  1. Khởi tạo biến đếm số lượng ước: int dem = 0;.
  2. Dùng vòng lặp for (int i = 1; i <= n; i++):
     • Nếu n % i == 0 (tức ~i~ là ước của ~n~):
       • In ~i~ ra màn hình kèm một dấu cách.
       • Tăng biến đếm: dem++;.
  3. Xuống dòng (cout << endl;).
  4. In ra dòng thống kê theo đúng định dạng đề bài: cout << "Tong so uoc: " << dem << endl;.

• *Xử lý chương trình chính (main): Do đề bài cho biết trước có đúng 4 số trên 4 dòng, ta có thể lặp 4 lần và gọi hàm lietKeUoc(n).

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(T \times N)~ với ~T = 4~ và ~N \le 10^5~, tương đương khoảng ~4 \times 10^5~ phép tính ~\rightarrow~ Chạy tức thì (~< 0.01~ giây).
  • Bộ nhớ: ~\mathcal{O}(1)~ — Không cần dùng mảng phụ lưu trữ.

4. Cài đặt mẫu (C++)

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

// Hàm tìm, in danh sách ước và số lượng ước của n
void lietKeUoc(int n) 
{
    int dem = 0;
    for (int i = 1; i <= n; i++) 
    {
        if (n % i == 0) 
        {
            cout << i << " ";
            dem++;
        }
    }
    cout << endl;
    cout << "Tong so uoc: " << dem << endl;
}

int main() {
    // Tối ưu nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    // Đọc 4 số theo dữ liệu vào
    for (int i = 1; i <= 4; i++) 
    {
        cin >> n;
        lietKeUoc(n);
    }
    return 0;
}