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
Đầu vào :
16
1048448 16256 1 1 16256 8 2 2 4194272 16 8 16 1984 4 4 65528
bạn nào chỉ giúp mình xem đầu vào này có kết quả thế nào ? mình tính mãi vẫn ra kết quả là 0.
Trong đây không có số hoàn hảo nào , cũng không có số nguyên tố nào , thì làm thế nào có kết quả khác 0 được ?
-
0
mduc209
12:20 a.m. 25 Tháng 9, 2024
3 bình luận nữakq 240 á