#1451. KDIV - Chia hết

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho dãy n số nguyên dương P=(p_1,p_2,…,p_n) và một số nguyên k\ (0≤k≤n) . Hãy xác định xem trong đoạn [a,b]\ (1≤a≤b≤10^9,b-a≤10^5) có bao nhiêu số nguyên chia hết cho đúng k số trong dãy số nguyên P ?

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên n k\ (1≤n≤10^5) ;
  • Dòng thứ hai chứa n số nguyên dương p_1,p_2,…,p_n\ (1≤p_i≤10^9) ;
  • Dòng thứ ba chứa hai số nguyên a b .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Dữ liệu vào:
2 1
2 3
1 10
Dữ liệu ra:
6
Giải thích:
  • Trong đoạn [1,10] có đúng 6 số nguyên chỉ chia hết cho 1 số trong dãy (2,3) là: 2, 3, 4, 8, 9, 10 .
Dữ liệu vào:
2 1
2 2
1 10
Dữ liệu ra:
0