Đếm số chia hết

Xem PDF

Điểm: 300 Thời gian: 3.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(n\) số tự nhiên \(a_1, a_2, ..., a_n\). Hãy xác định xem có bao nhiêu số \(x\) trong đoạn \([l, r]\)\(x\) không chia hết cho số \(a_i\) nào cả.

Input

  • Dòng đầu tiên chứa 3 số nguyên dương \(n, l, r \ (1 \leq n \leq 18)\)
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

  • In ra một số nguyên là đáp số bài toán

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(1 \leq l \leq r \leq 10^6\)
  • Subtask \(2\) (\(70\%\) số điểm): \(1 \leq l \leq r \leq 10^{18}\)

Example

Test 1

Input
3 10 20
3 4 5 
Output
5

Bình luận