Bộ số hoàn hảo

Xem PDF
Tác giả:
flo
Dạng bài
Đ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