[Buổi 4][Tiền xử lý số học & truy vấn số nguyên][HW] Bài 2: Bộ đếm ước cho lô dữ liệu
Bộ đếm ước cho lô dữ liệu
Bối cảnh và bài toán
Một hệ thống phân loại vật liệu nhận n mã số nguyên dương. Chỉ số phân loại của mỗi mã bằng số lượng ước dương của mã đó.
Dữ liệu được xử lý theo lô lớn, nên chương trình cần trả kết quả cho toàn bộ mã trong giới hạn thời gian.
Yêu cầu
Với mỗi số x, hãy tính số lượng ước dương của x.
Input
- Dòng 1: số nguyên
n. ndòng tiếp theo: mỗi dòng chứa một số nguyênx.
Output
Với mỗi x, in số lượng ước dương của nó trên một dòng.
Ràng buộc
1 <= n <= 10^51 <= x <= 10^6
Chấm điểm
| Subtask | Điểm | Điều kiện | Official tests |
|---|---|---|---|
| S1 | 20% | n ≤ 100, x ≤ 10^4 | 01–04 |
| S2 | 30% | n ≤ 5000, x ≤ 10^6 | 05–10 |
| S3 | 50% | Không có ràng buộc bổ sung | 11–20 |
Ví dụ 1
Input
3
16
17
18
Output
5
2
6
Giải thích. 16 có 5 ước, 17 là số nguyên tố có 2 ước, còn 18 có 6 ước.
Ví dụ 2
Input
4
1
4
12
36
Output
1
3
6
9
Giải thích. 1 có một ước; 4=2^2 có 3 ước; 12=2^2*3 có 6 ước.
Thông tin bài tập
| Thuộc tính | Giá trị |
|---|---|
| Mã bài | DSA-M02-B04-HW02 |
| Buổi | B04 |
| Loại bài | HOMEWORK |
| Mức độ khó | Trung bình (Medium) |
| Thời gian làm bài khuyến nghị | 25 phút |
| Time limit | 1 giây |
| Memory limit | 256 MB |
| Tổng điểm | 100 |
| Chuẩn ngôn ngữ tham chiếu | C++17 |
Nguồn: Phỏng theo CSES Problem Set — Counting Divisors (Task 1713). Tham khảo: https://cses.fi/problemset/task/1713/
Comments