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\)\(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
4

Test 2

Input
12 2
1 1 2 3 4 5 6 7 8 9 10 11 
Output
8
Note
  • 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


  • 0
    ltt_huy    2:14 p.m. 3 Tháng 11, 2020

    contest này có sol ko ạ


    • 2
      SPyofgame    6:19 p.m. 3 Tháng 11, 2020

      Có bạn 😃


      • 0
        ktonh123    9:39 a.m. 4 Tháng 11, 2020

        Sol ở đâu vậy bạn


        • 0
          SPyofgame    9:56 a.m. 4 Tháng 11, 2020

          Tối nay sẽ có solution bạn 😃


          • 0
            ktonh123    7:05 p.m. 4 Tháng 11, 2020

            mình hóng sol ở đâu vậy bạn :v


            • 1
              SPyofgame    7:10 p.m. 4 Tháng 11, 2020

              Mình đang viết solution ở đây ạ :v