#1118. LOTTERY - Xổ số

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

NGUỒN: VOI Training Camp 3H Task ACM

Các rô-bốt trong khu mỏ có số xê ri liên tục trong khoảng [a, b]\ (1 ≤ a ≤ b ≤ 10^9, b – a ≤ 10^5) . Vì điều kiện thời tiết xấu chỉ có một lô hàng mỡ bôi trơn được chở tới. Lô hàng này không đủ cho tất cả các rô-bốt. Người ta quyết định tổ chức một cuộc “xổ số” nhỏ phân phối số mỡ này: Dùng máy tính đưa ra n số nguyên dương p_1, p_2, . . ., p_n và một số nguyên k\ (0 ≤ k ≤ n) . Những rô-bốt nào có số xê ri chia hết cho đúng k số trong dãy số nguyên (p_i) sẽ được thay mỡ mới.

Yêu cầu: Hãy cho biết số lượng rô-bốt được thay mỡ.

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 p_1, p_2, . . ., p_n (1 ≤ p_i ≤ 10^9, \forall i)
  • 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