Bộ số hoàn hảo
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Just a random problem ...
Như chúng ta đã biết, số nguyên dương \(n\) là số hoàn hảo khi và chỉ khi tổng các ước nguyên dương của \(n\) là \(2\times n\). Một vài số hoàn hảo đầu tiên là:
- Số \(6\) vì \(1 + 2 + 3 + 6 = 2 \times 6\).
- Số \(28\) vì \(1 + 2 + 4 + 7 + 14 + 28 = 2 \times 28\).
- \(...\)
Cho dãy \(a\) gồm \(n\) phần tử, một bộ số \((i_1, i_2, ..., i_k)\) được gọi là hoàn hảo nếu:
- \(1 \le i_1 < i_2 < ... < i_k \le n\) \((1 \le k \le n)\).
- \(a_{i_1}\times a_{i_2}\) \(\times\) \(...\) \(\times\) \(a_{i_k}\) là một số hoàn hảo.
Với dãy \(a\) đã cho, nhiệm vụ của bạn là đếm số lượng bộ số hoàn hảo của nó.
Input, Output and Scoring
Input
- Số nguyên dương \(n\) \((1 \le n \le 2^{20}-1)\).
- Dãy \(a\) gồm \(n\) phần tử \(a_1, a_2, ..., a_n\) \((1 \le a_i \le 2^{128}-1)\).
Output
- In ra kết quả sau khi chia lấy dư cho \(1234567891\).
Scoring
- Subtask \(1\) \((8\%)\): \(n = 1; 1 \le a_i \le 2^{42}-1\).
- Subtask \(2\) \((10\%)\): \(1 \le n, a_i \le 2^3-1\).
- Subtask \(3\) \((12\%)\): \(n = 1\).
- Subtask \(4\) \((14\%)\): \(1 \le n \le 20\).
- Subtask \(5\) \((16\%)\): \(1 \le n \le 40\).
- Subtask \(6\) \((18\%)\): \(1 \le n \le 2^{10}-1\).
- Subtask \(7\) \((22\%)\): Không giới hạn gì thêm.
Test
Input
5
4 7 6 1 3
Output
4
Note
- Có \(4\) bộ số hoàn hảo là \((1, 2), (1, 2, 4), (3)\) và \((3, 4)\).
Nguồn: Từ đâu đó ở TLEoj
Bình luận
Test chấm của bài mới được cập nhật nhé. Mục đích chính là thách bạn uyvu1312 if test bài này.
-
0
trieunguyen_a1
2:39 a.m. 3 Tháng 4, 2024
-
1
flo
11:07 p.m. 3 Tháng 4, 2024
←
chỉnh sửa 3
→
-
0
quananhnguyen
9:28 p.m. 30 Tháng 3, 2024
←
đã chỉnh sửa
→
1 bình luận nữaCho tôi xin sol được không ông
Theo định lý Euclid-Euler, số nguyên dương \(n\) là số hoàn hảo khi và chỉ khi \(n\) chẵn và \(n = 2^{p-1} \times (2^p-1)\) với \(2^p-1\) là một số nguyên tố Mersenne. Đây là gợi ý máu chốt của bài, phần còn lại bạn tự giải quyết 🙂
Còn về số hoàn hảo lẻ thì vẫn chưa chắc rằng nó có tồn tại hay không nên ta sẽ không đề cập trong bài này.
...