Bội P
Xem PDF
Điểm:
350 (p)
Thời gian:
2.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Lương có \(n\) viên bi, viên bi thứ \(i\) được ghi số \(a_i\). Lương muốn chọn ra một vài viên bi để tặng cho bạn gái. Tuy nhiên, Lương biết rằng bạn gái rất ghét số \(P\), nên anh quyết định rằng: Trong những viên bi được chọn, không được có 2 viên bi phân biệt \(x,y\) nào mà \(\frac{a_x}{a_y}=P\). Bạn hãy tính xem số bi nhiều nhất mà Lương có thể tặng bạn gái là bao nhiêu.
Input
- Dòng đầu tiên chứa hai số nguyên dương \(n,P\) \((1 \leq n \leq 10^5, 1 \leq P \leq 10^{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^{18})\)
Output
- In ra một dòng là số bi lớn nhất mà Lương có thể tặng bạn gái.
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(P = 1\).
- Subtask \(2\) (\(3\%\) số điểm): \(1 \leq a_i \leq 20\) và \(P \leq 20\).
- Subtask \(3\) (\(50\%\) số điểm): không có thêm điều kiện gì.
Example
Test 1
Input
5 4
1 2 3 4 5 Output
4Test 2
Input
12 2
1 1 2 3 4 5 6 7 8 9 10 11 Output
8Note
- Trong ví dụ 1, Lương có thể tặng bạn gái các viên bi đánh số \(1,2,3,5\) (Lương có đánh rơi nhịp nào không? :)).
- Trong ví dụ 2, Lương có thể tặng bạn gái các viên bi đánh số \(1,1,3,4,5,7,9,11\).
Bình luận
contest này có sol ko ạ
Có bạn 😃
Sol ở đâu vậy bạn
Tối nay sẽ có solution bạn 😃
mình hóng sol ở đâu vậy bạn :v
Mình đang viết solution ở đây ạ :v