Đếm số chia hết

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
cuom1999
Dạng bài
Đ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]\) mà \(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