Elearning CodePath – CTP Online Judge

Tổng các ước thực sự (DIVSUM)

DIVSUM

🟢 Hard #Math #Number Theory

### 📝 Bài toán
Cho số tự nhiên n. Một ước thực sự của n được định nghĩa là ước của n và phải nhỏ hơn n.
Yêu cầu: Tính tổng của tất cả các ước thực sự của n.
Ví dụ: Số 20 có 5 ước thực sự là {1, 2, 4, 5, 10}. Tổng các ước này là: 1 + 2 + 4 + 5 + 10 = 22.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file văn bản DIVSUM.INP:
* Dòng đầu tiên chứa số nguyên T là số lượng bộ dữ liệu (test cases).
* T dòng tiếp theo, mỗi dòng chứa một số nguyên n.

Giới hạn:
* T xấp xỉ 200,000.
* 1 <= n <= 500,000.

### 📤 Định dạng Đầu ra
Ghi ra file văn bản DIVSUM.OUT:
* Với mỗi số nguyên n, in ra một số nguyên duy nhất là tổng các ước thực sự của nó trên một dòng.

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 3 | |
| 2 | 1 |
| 10 | 8 |
| 20 | 22 |

Giải thích ví dụ:
* n = 2: Ước thực sự là {1}. Tổng = 1.
* n = 10: Ước thực sự là {1, 2, 5}. Tổng = 1 + 2 + 5 = 8.
* n = 20: Ước thực sự là {1, 2, 4, 5, 10}. Tổng = 22.

### 🏷 Subtasks
| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | T <= 100; n <= 10^4 | 30% |
| 2 | T <= 2*10^5; n <= 5*10^5 | 70% |

✅ Đã AC: 3 / 5 submissions